#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T abs(T a) {
  return ((a < 0) ? -a : a);
}
template <typename T>
inline T sqr(T a) {
  return a * a;
}
const int INF = (int)1E9 + 7;
const long double EPS = 1E-9;
const long double PI = 3.1415926535897932384626433832795;
const int NMAX = 100000;
int p[2][NMAX], t[2][NMAX], n[2], m;
char c[2][NMAX];
long long ans[NMAX];
int nx[NMAX][40], sznx = 0;
vector<int> tnx[NMAX];
vector<pair<int, char> > g[NMAX];
void dfs(int v, int r) {
  if (r == -1) return;
  int curt = t[1][v];
  for (int i = 0; i < int(int((tnx[r]).size())); ++i) {
    int stt = max(tnx[r][i], curt);
    ans[stt]++;
    ans[m + 10]--;
  }
  for (int i = 0; i < int(int((g[v]).size())); ++i) {
    int u = g[v][i].first;
    char c = g[v][i].second;
    dfs(u, nx[r][c - 'a']);
  }
}
int main() {
  scanf("%d", &m);
  n[0] = n[1] = 1;
  memset(p, -1, sizeof p);
  memset(t, 63, sizeof t);
  memset(c, 0, sizeof c);
  t[0][0] = t[1][0] = 0;
  for (int si = 1; si <= int(m); ++si) {
    int ti, vi;
    char ci;
    scanf(" %d %d %c ", &ti, &vi, &ci);
    ti--, vi--;
    p[ti][n[ti]] = vi;
    c[ti][n[ti]] = ci;
    t[ti][n[ti]] = si;
    if (ti == 1) g[vi].push_back(make_pair(n[1], ci));
    n[ti]++;
  }
  memset(nx, -1, sizeof nx);
  sznx = 1;
  for (int v = 0; v < int(n[0]); ++v) {
    int r = 0;
    for (int cv = v; cv != 0; cv = p[0][cv]) {
      int& u = nx[r][c[0][cv] - 'a'];
      if (u == -1) {
        u = sznx++;
      }
      r = u;
    }
    tnx[r].push_back(t[0][v]);
  }
  for (int v = 0; v < int(n[1]); ++v) dfs(v, 0);
  for (int i = int(1); i < int(m + 10); ++i) ans[i] += ans[i - 1];
  for (int st = 1; st <= int(m); ++st) cout << ans[st] << endl;
  return 0;
}
