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 
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class D{
    public static void main(String args[]) throws InterruptedException {
        Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
            @Override
            public void run() {
                InputStream inputStream = System.in;
                OutputStream outputStream = System.out;
                InputReader in = new InputReader(inputStream);
                PrintWriter out = new PrintWriter(outputStream);
                Solver solver = new Solver();
                solver.solve(in, out);
                out.close();
            }
        };
        t.start();
        t.join();
    }
    static class Solver  {
        int mx = (int) 5e5;
        int mxb = (1 << 22) + 10;
        ArrayList<Integer> g[]=new ArrayList[mx];
        int sz[] = new int[mx];
        int lyr[] = new int[mx];
        int ch[] = new int[mx];
        int f[] = new int[mx];
        ArrayList<Pt>ml[]=new ArrayList[mx];
        int deepest[] = new int[mxb];

        void dfs(int u) {
            sz[u] = 1;
            int idx = 0;
            for (int i = 0; i < g[u].size(); i++) {
                int v = g[u].get(i);
                lyr[v] = 1 + lyr[u];
                dfs(v);
                sz[u] += sz[v];
                if (sz[v] > sz[g[u].get(idx)]) idx = i;
            }
            if (!g[u].isEmpty()) Collections.swap(g[u], idx, 0);
        }

        void go(int u, int b, boolean clr) {
            //out.println("go "+u+" lyr="+lyr[u]+" b="+b);
            f[u] = 0;
            for (int i = 1; i < g[u].size(); i++) {
                int v = g[u].get(i);
                go(v, b ^ (1 << ch[v]), true);
                f[u] = Math.max(f[u], f[v]);
            }
            if (g[u].isEmpty()) {
                ml[u].add(new Pt(b, lyr[u]));
                deepest[b] = Math.max(deepest[b], lyr[u]);
            }
            else{
                int z = g[u].get(0);
                go(z, b ^ (1 << ch[z]), false);
                f[u] = Math.max(f[u], f[z]);
                int mask = b;
                if (deepest[mask] != -1) f[u] = Math.max(f[u], deepest[mask] - lyr[u]);
                for (int j = 0; j < 22; j++) {
                    mask = (b ^ (1 << j));
                    if (deepest[mask] != -1) f[u] = Math.max(f[u], deepest[mask] - lyr[u]);
                }
                ml[u]=ml[z];
                ml[u].add(new Pt(b, lyr[u]));
                deepest[b] = Math.max(deepest[b], lyr[u]);
                for (int i = 1; i < g[u].size(); i++) {
                    int v = g[u].get(i);
                    for (Pt p : ml[v]) {
                        mask = p.x;
                        if (deepest[mask] != -1) {
                            int bet = p.y + deepest[mask] - 2 * lyr[u];
                            f[u] = Math.max(f[u], bet);
                        }
                        for (int j = 0; j < 22; j++) {
                            mask = (p.x ^ (1 << j));
                            if (deepest[mask] != -1) {
                                int bet = p.y + deepest[mask] - 2 * lyr[u];
                                f[u] = Math.max(f[u], bet);
                            }
                        }
                    }
                    for (Pt p : ml[v]) {
                        deepest[p.x] = Math.max(deepest[p.x], p.y);
                        ml[u].add(p);
                    }
                }
            }


            if (clr) for (Pt p : ml[u]) deepest[p.x] = -1;
        }

        void solve(InputReader in, PrintWriter out){
            int n = in.nextInt();
            for (int i = 0; i < n; i++) {
                g[i]=new ArrayList<Integer>();
                ml[i]=new ArrayList<Pt>();
            }
            Arrays.fill(deepest, -1);
            for (int i = 1; i < n; i++) {
                int pi = in.nextInt() - 1;
                g[pi].add(i);
                String s = in.next();
                ch[i] = s.charAt(0) - 'a';
            }
            dfs(0);
            go(0, 0, true);
            for (int i = 0; i < n; i++) out.print(f[i] + " ");
        }
    }
    static class Pt {
        public int x,y;

        public Pt(int _x, int _y) {
            x=_x;
            y=_y;
        }
    }
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}