#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int n, x, y, h[100005], sz[100005], p[100005];
long long _pow[100005], v[2][100005], ret;
char s[5];
map<int, int> M[2];
map<int, int>::iterator itr;
int main() {
  scanf("%d", &n);
  _pow[0] = 1;
  for (int i = (0); i < (n); i++) _pow[i + 1] = (_pow[i] * 26) % MOD;
  sz[0] = sz[1] = 1;
  h[1] = -1;
  for (int i = (0); i < (n); i++) {
    scanf("%d%d%s", &x, &y, s), x--;
    if (x == 0) {
      sz[0]++;
      h[sz[0]] = h[y] + 1;
      v[0][sz[0]] = (v[0][y] + (s[0] - 'a' + 1) * _pow[h[sz[0]]]) % MOD;
      M[0][v[0][sz[0]]]++;
    }
    if (x == 1) {
      sz[1]++;
      v[1][sz[1]] = (v[1][y] * 26 + (s[0] - 'a' + 1)) % MOD;
      p[sz[1]] = y;
      int t = sz[1], off = 0;
      long long val;
      while (t != 1) {
        t = p[t];
        val = v[1][sz[1]] - v[1][t] * _pow[++off];
        val = (val % MOD + MOD) % MOD;
        M[1][val]++;
      }
    }
    ret = 0;
    for (itr = M[0].begin(); itr != M[0].end(); itr++) {
      ret += (long long)(itr->second) * (long long)M[1][itr->first];
    }
    printf("%I64d\n", ret + sz[1]);
  }
  return 0;
}
