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;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline long long read1() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int N = 5e5 + 10;
vector<int> v[N];
bool used[N];
int ans[N], glub[N];
struct S {
  int Xor = 0;
  int add = 0;
  int mx = 0;
  unordered_map<int, int> m;
};
char s[N];
S dfs(int x, int cur = 0) {
  S res;
  res.m[0] = 0;
  int nowAns = 0;
  glub[x] = cur;
  for (int to : v[x]) {
    nowAns = max(nowAns, 1);
    auto f = dfs(to, cur + 1);
    nowAns = max(nowAns, ans[to]);
    f.add++;
    char c = s[to];
    f.Xor ^= (1 << c);
    if (f.m.size() > res.m.size()) swap(f, res);
    for (auto p : f.m) {
      int key = p.first ^ f.Xor ^ res.Xor;
      int val = p.second + f.add + res.add;
      if (val + res.mx <= nowAns) continue;
      for (int mask = 0; mask < (1 << 22);) {
        int what = key ^ mask;
        auto it = res.m.find(what);
        if (it != res.m.end()) nowAns = max(nowAns, val + it->second);
        if (!mask)
          mask++;
        else
          mask <<= 1;
      }
    }
    for (auto p : f.m) {
      int key = p.first ^ f.Xor ^ res.Xor;
      int val = p.second + f.add - res.add;
      res.mx = max(res.mx, val);
      if (!res.m.count(key))
        res.m[key] = val;
      else
        res.m[key] = max(res.m[key], val);
    }
  }
  ans[x] = nowAns;
  return res;
}
int main() {
  int n = read();
  for (int i = 1; i <= n - 1; i++) {
    char c;
    int x = read();
    c = getchar();
    x--;
    v[x].push_back(i);
    s[i] = c - 'a';
  }
  dfs(0);
  for (int i = 0; i < (n); i++) printf("%d ", ans[i]);
  return 0;
}
