package main

import (
	"io"
	"os"
	"strconv"
)

var data []byte
var ptr int

func nextInt() int {
	for ptr < len(data) && (data[ptr] < '0' || data[ptr] > '9') {
		ptr++
	}
	v := 0
	for ptr < len(data) && data[ptr] >= '0' && data[ptr] <= '9' {
		v = v*10 + int(data[ptr]-'0')
		ptr++
	}
	return v
}

func nextByte() byte {
	for ptr < len(data) && (data[ptr] == ' ' || data[ptr] == '\n' || data[ptr] == '\r' || data[ptr] == '\t') {
		ptr++
	}
	b := data[ptr]
	ptr++
	return b
}

var up [][]int
var rk [][]int
var stateLen []int
var stateCh []int
var K int

func charAtC(s, pos int) int {
	d := pos - 1
	bit := 0
	for d > 0 {
		if d&1 == 1 {
			s = up[bit][s]
		}
		d >>= 1
		bit++
	}
	return stateCh[s]
}

func lcpC(u, v int) int {
	if u == v {
		return stateLen[u]
	}
	ru := stateLen[u]
	rv := stateLen[v]
	ans := 0
	for k := K; k >= 0; k-- {
		step := 1 << k
		if ru >= step && rv >= step && rk[k][u] == rk[k][v] {
			ans += step
			ru -= step
			rv -= step
			u = up[k][u]
			v = up[k][v]
		}
	}
	return ans
}

type BIT struct {
	n   int
	bit []int64
}

func NewBIT(n int) *BIT {
	return &BIT{n: n, bit: make([]int64, n+2)}
}

func (b *BIT) Add(i int, v int64) {
	for i <= b.n {
		b.bit[i] += v
		i += i & -i
	}
}

func (b *BIT) Sum(i int) int64 {
	var r int64
	for i > 0 {
		r += b.bit[i]
		i -= i & -i
	}
	return r
}

func main() {
	data, _ = io.ReadAll(os.Stdin)
	n := nextInt()

	par1 := make([]int, n+2)
	par2 := make([]int, n+2)
	lab1 := make([]byte, n+2)
	lab2 := make([]byte, n+2)
	opsTree := make([]byte, n)
	opsNew := make([]int, n)

	m1, m2 := 1, 1
	for i := 0; i < n; i++ {
		t := nextInt()
		v := nextInt()
		c := nextByte()
		if t == 1 {
			m1++
			par1[m1] = v
			lab1[m1] = c
			opsTree[i] = 1
			opsNew[i] = m1
		} else {
			m2++
			par2[m2] = v
			lab2[m2] = c
			opsTree[i] = 2
			opsNew[i] = m2
		}
	}

	frontChild := make([][26]int, m2+2)
	cStateOfVertex := make([]int, m2+2)
	stateLen = make([]int, m2+2)
	stateCh = make([]int, m2+2)
	stateParent := make([]int, m2+2)

	stateCnt := 1
	maxLen := 0
	for v := 2; v <= m2; v++ {
		ps := cStateOfVertex[par2[v]]
		ci := int(lab2[v] - 'a')
		ns := frontChild[ps][ci]
		if ns == 0 {
			ns = stateCnt
			stateCnt++
			frontChild[ps][ci] = ns
			stateParent[ns] = ps
			stateCh[ns] = ci + 1
			stateLen[ns] = stateLen[ps] + 1
			if stateLen[ns] > maxLen {
				maxLen = stateLen[ns]
			}
		}
		cStateOfVertex[v] = ns
	}
	stateLen = stateLen[:stateCnt]
	stateCh = stateCh[:stateCnt]
	stateParent = stateParent[:stateCnt]

	K = 0
	for (1 << K) <= maxLen {
		K++
	}

	up = make([][]int, K+1)
	rk = make([][]int, K+1)
	up[0] = make([]int, stateCnt)
	rk[0] = make([]int, stateCnt)
	for i := 0; i < stateCnt; i++ {
		up[0][i] = stateParent[i]
		rk[0][i] = stateCh[i]
	}

	rankCnt := 27
	order := make([]int, stateCnt)
	tmp := make([]int, stateCnt)
	cntSize := stateCnt
	if cntSize < 27 {
		cntSize = 27
	}
	cnt := make([]int, cntSize)

	for k := 1; k <= K; k++ {
		prevR := rk[k-1]
		prevUp := up[k-1]
		curUp := make([]int, stateCnt)
		curR := make([]int, stateCnt)
		up[k] = curUp
		rk[k] = curR

		for i := 0; i < stateCnt; i++ {
			curUp[i] = prevUp[prevUp[i]]
		}

		for i := 0; i < rankCnt; i++ {
			cnt[i] = 0
		}
		for i := 0; i < stateCnt; i++ {
			cnt[prevR[prevUp[i]]]++
		}
		s := 0
		for i := 0; i < rankCnt; i++ {
			c := cnt[i]
			cnt[i] = s
			s += c
		}
		for i := 0; i < stateCnt; i++ {
			key := prevR[prevUp[i]]
			tmp[cnt[key]] = i
			cnt[key]++
		}

		for i := 0; i < rankCnt; i++ {
			cnt[i] = 0
		}
		for i := 0; i < stateCnt; i++ {
			cnt[prevR[tmp[i]]]++
		}
		s = 0
		for i := 0; i < rankCnt; i++ {
			c := cnt[i]
			cnt[i] = s
			s += c
		}
		for i := 0; i < stateCnt; i++ {
			id := tmp[i]
			key := prevR[id]
			order[cnt[key]] = id
			cnt[key]++
		}

		curRank := 0
		curR[order[0]] = 0
		for i := 1; i < stateCnt; i++ {
			a := order[i-1]
			b := order[i]
			if prevR[a] != prevR[b] || prevR[prevUp[a]] != prevR[prevUp[b]] {
				curRank++
			}
			curR[b] = curRank
		}
		rankCnt = curRank + 1
	}

	orderByRank := make([]int, stateCnt)
	for i := 0; i < stateCnt; i++ {
		orderByRank[rk[K][i]] = i
	}
	sortedC := make([]int, 0, stateCnt-1)
	for i := 0; i < stateCnt; i++ {
		if orderByRank[i] != 0 {
			sortedC = append(sortedC, orderByRank[i])
		}
	}

	maxNodes := 2*stateCnt + m1 + 5
	childTrie := make([][26]int, maxNodes)
	nodeDepth := make([]int, maxNodes)
	nodeRep := make([]int, maxNodes)
	cStateNode := make([]int, stateCnt)
	cStateNode[0] = 1
	nodeCnt := 1

	if len(sortedC) > 0 {
		stack := make([]int, 0, maxNodes)

		s0 := sortedC[0]
		nodeCnt++
		leaf := nodeCnt
		nodeDepth[leaf] = stateLen[s0]
		nodeRep[leaf] = s0
		childTrie[1][charAtC(s0, 1)-1] = leaf
		cStateNode[s0] = leaf
		stack = append(stack, 1, leaf)
		prev := s0

		for i := 1; i < len(sortedC); i++ {
			cur := sortedC[i]
			l := lcpC(prev, cur)

			child := 0
			for nodeDepth[stack[len(stack)-1]] > l {
				child = stack[len(stack)-1]
				stack = stack[:len(stack)-1]
			}
			p := stack[len(stack)-1]

			if nodeDepth[p] < l {
				nodeCnt++
				mid := nodeCnt
				nodeDepth[mid] = l
				nodeRep[mid] = nodeRep[child]
				idx1 := charAtC(nodeRep[child], nodeDepth[p]+1) - 1
				childTrie[p][idx1] = mid
				idx2 := charAtC(nodeRep[child], l+1) - 1
				childTrie[mid][idx2] = child
				stack = append(stack, mid)
				p = mid
			}

			nodeCnt++
			leaf = nodeCnt
			nodeDepth[leaf] = stateLen[cur]
			nodeRep[leaf] = cur
			idx := charAtC(cur, nodeDepth[p]+1) - 1
			childTrie[p][idx] = leaf
			cStateNode[cur] = leaf
			stack = append(stack, leaf)
			prev = cur
		}
	}

	map1 := make([]int, m1+1)
	map1[1] = 1
	for v := 2; v <= m1; v++ {
		p := map1[par1[v]]
		if p == 0 {
			continue
		}
		ci := int(lab1[v] - 'a')
		ch := childTrie[p][ci]
		if ch == 0 {
			continue
		}
		if nodeDepth[ch] == nodeDepth[p]+1 {
			map1[v] = ch
		} else {
			nodeCnt++
			mid := nodeCnt
			nodeDepth[mid] = nodeDepth[p] + 1
			nodeRep[mid] = nodeRep[ch]
			childTrie[p][ci] = mid
			idx2 := charAtC(nodeRep[ch], nodeDepth[p]+2) - 1
			childTrie[mid][idx2] = ch
			map1[v] = mid
		}
	}

	tin := make([]int, nodeCnt+1)
	tout := make([]int, nodeCnt+1)
	stNodes := make([]int, 0, nodeCnt)
	stPos := make([]int, 0, nodeCnt)
	stNodes = append(stNodes, 1)
	stPos = append(stPos, 0)
	timer := 0
	for len(stNodes) > 0 {
		top := len(stNodes) - 1
		u := stNodes[top]
		pos := stPos[top]
		if pos == 0 {
			timer++
			tin[u] = timer
		}
		for pos < 26 && childTrie[u][pos] == 0 {
			pos++
		}
		if pos == 26 {
			tout[u] = timer
			stNodes = stNodes[:top]
			stPos = stPos[:top]
		} else {
			stPos[top] = pos + 1
			v := childTrie[u][pos]
			stNodes = append(stNodes, v)
			stPos = append(stPos, 0)
		}
	}

	bitAnc := NewBIT(timer)
	bitSub := NewBIT(timer)

	bitAnc.Add(tin[1], 1)
	bitSub.Add(tin[1], 1)

	var ans int64 = 1
	out := make([]byte, 0, n*12)

	for i := 0; i < n; i++ {
		if opsTree[i] == 1 {
			v := opsNew[i]
			node := map1[v]
			if node != 0 {
				ans += bitSub.Sum(tout[node]) - bitSub.Sum(tin[node]-1)
				bitAnc.Add(tin[node], 1)
				if tout[node]+1 <= timer {
					bitAnc.Add(tout[node]+1, -1)
				}
			}
		} else {
			v := opsNew[i]
			node := cStateNode[cStateOfVertex[v]]
			ans += bitAnc.Sum(tin[node])
			bitSub.Add(tin[node], 1)
		}
		out = strconv.AppendInt(out, ans, 10)
		out = append(out, '\n')
	}

	os.Stdout.Write(out)
}