Just in case somebody missed it: we have wonderful girls in Arpa’s land.

Arpa has a rooted tree (connected acyclic graph) consisting of n vertices. The vertices are numbered 1 through n, the vertex 1 is the root. There is a letter written on each edge of this tree. Mehrdad is a fan of Dokhtar-kosh things. He call a string Dokhtar-kosh, if we can shuffle the characters in string such that it becomes palindrome.

<image>

He asks Arpa, for each vertex v, what is the length of the longest simple path in subtree of v that form a Dokhtar-kosh string.

Input

The first line contains integer n (1 ≤ n ≤ 5·105) — the number of vertices in the tree.

(n - 1) lines follow, the i-th of them contain an integer pi + 1 and a letter ci + 1 (1 ≤ pi + 1 ≤ i, ci + 1 is lowercase English letter, between a and v, inclusively), that mean that there is an edge between nodes pi + 1 and i + 1 and there is a letter ci + 1 written on this edge.

Output

Print n integers. The i-th of them should be the length of the longest simple path in subtree of the i-th vertex that form a Dokhtar-kosh string.

Examples

Input

4
1 s
2 a
3 s


Output

3 1 1 0 

Input

5
1 a
2 h
1 a
4 h


Output

4 1 0 1 0 
#include <bits/stdc++.h>
using namespace std;
struct st1 {
  int n, v;
};
int a, b, c, d, e, n, ans[500007], num[500007];
int inf = 1000000007;
int two[107] = {0}, bj1, bj2;
vector<int> q[500007], vs;
vector<st1> w[500007];
int s[5000007];
char x[500007];
void sou0(int x1, int fa) {
  num[x1] = 1;
  for (int i = 1; i <= q[x1].size(); i++)
    if (q[x1][i - 1] != fa) {
      sou0(q[x1][i - 1], x1);
      num[x1] += num[q[x1][i - 1]];
    }
}
void sou(int x1, int fa, int save) {
  if (num[x1] == 1) return;
  int ma = 0, big = 0, ans1 = 0;
  for (int i = 1; i <= q[x1].size(); i++)
    if (q[x1][i - 1] != fa && num[q[x1][i - 1]] > ma)
      ma = num[q[x1][i - 1]], big = q[x1][i - 1];
  for (int i = 1; i <= q[x1].size(); i++)
    if (q[x1][i - 1] != fa && q[x1][i - 1] != big) sou(q[x1][i - 1], x1, 0);
  sou(big, x1, 1);
  for (int i = 1; i <= q[x1].size(); i++)
    if (q[x1][i - 1] != fa) ans1 = max(ans1, ans[q[x1][i - 1]]);
  if (s[bj1] == -inf) vs.push_back(bj1);
  s[bj1] = max(s[bj1], -bj2);
  bj1 ^= two[x[big] - 96];
  bj2++;
  for (int i = 1; i <= q[x1].size(); i++)
    if (q[x1][i - 1] != fa && q[x1][i - 1] != big) {
      int e = q[x1][i - 1];
      w[e].push_back(st1{0, 0});
      for (int j = 1; j <= w[e].size(); j++) {
        for (int k = 0; k <= 22; k++) {
          int f = w[e][j - 1].n ^ two[x[e] - 96] ^ bj1 ^ two[k];
          ans1 = max(ans1, w[e][j - 1].v + s[f] + bj2 + 1);
        }
      }
      for (int j = 1; j <= w[e].size(); j++) {
        int f = w[e][j - 1].n ^ two[x[e] - 96] ^ bj1;
        if (s[f] == -inf) vs.push_back(f);
        s[f] = max(s[f], w[e][j - 1].v - bj2 + 1);
      }
    }
  for (int k = 0; k <= 22; k++) ans1 = max(ans1, s[two[k] ^ bj1] + bj2);
  if (!save) {
    for (int i = 1; i <= vs.size(); i++) {
      w[x1].push_back(st1{vs[i - 1] ^ bj1, s[vs[i - 1]] + bj2});
      s[vs[i - 1]] = -inf;
    }
    vs.clear();
    bj1 = 0;
    bj2 = 0;
  }
  ans[x1] = ans1;
}
int main() {
  two[1] = 1;
  for (int i = 2; i <= 22; i++) two[i] = two[i - 1] * 2;
  scanf("%d", &n);
  for (int i = 0; i <= 1 << 22; i++) s[i] = -inf;
  for (int i = 2; i <= n; i++) {
    scanf("%d%s", &a, &x[i]);
    q[a].push_back(i);
  }
  sou0(1, 0);
  sou(1, 0, 1);
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}
