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.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.List;
import java.util.ArrayList;

public class D {
	public static void main(String[] args) {
		/*try {
			//InputReader in = new InputReader(new File("test.inp"));
			//PrintWriter out = new PrintWriter(new File("test.out"));
		} catch (IOException e) {
			throw new RuntimeException(e);
		}*/
		Thread thread = new Thread(null, null, "task", Runtime.getRuntime().maxMemory()) {
			public void run() {
				//try {
					InputStream inputStream = System.in;					
					InputReader in = new InputReader(inputStream);
					OutputStream outputStream = System.out;
					PrintWriter out = new PrintWriter(outputStream);
					//InputReader in = new InputReader(new File("test.inp"));
					//PrintWriter out = new PrintWriter(new File("test.out"));
					Task solver = new Task();
					solver.solve(in,out);
					out.close();
				//} catch (Exception e) {
				//	throw new RuntimeException(e);
				//}
				
			}
		};
		try {
			thread.run();
			thread.join();
		} catch (Exception e) {
			throw (new RuntimeException(e));
		}
	}
	
	static class Task {
		static int MAXN = 500005;
		static int MAXM = 5000006;
		class Edge {
			public int v, c;
			Edge(int _v, int _c) {
				v = _v;
				c = _c;
			}	
		}
		class MyAns {
			public int res;
			MyAns() { 
				res = 0;
			}
			MyAns(int v) {
				res = v;
			}
			void getMax(int v) {
				res = Math.max(res, v);
			}
		}
		
		int n;
		List <Edge> ke[] = new ArrayList[MAXN];
		int sz[] = new int[MAXN];
		int mask[] = new int[MAXN];
		int f[] = new int[MAXM];
		int h[] = new int[MAXN];
		int kq[] = new int[MAXN];
		
		void nhap(InputReader in) {
			n = in.readInt();
			for(int i=1; i<=n; i++)
				ke[i] = new ArrayList <Edge> ();
			for(int u=2; u<=n; u++) {
				int cha = in.readInt();
				String c = in.next();
				ke[cha].add(new Edge(u, c.charAt(0) - 'a'));
			}
		}
		
		public void solve(InputReader in, PrintWriter out) {
			nhap(in);
			for(int i=1; i<MAXM; i++) {
				f[i] = (int)(-1e9);
			}
			h[1] = 0;
			mask[1] = 0;
			dfsCallSize(1);
			dfs(1, true);
			for(int i=1; i<=n; i++)
				out.print(kq[i] + " ");
		}
		
		void dfsCallSize(int u) {
			sz[u] = 1;
			for(Edge e : ke[u]) {
				mask[e.v] = mask[u] ^ (1 << e.c);
				h[e.v] = h[u] + 1;
				dfsCallSize(e.v);
				sz[u] += sz[e.v];
			}
		}
		
		void add(int u) {
			f[mask[u]] = Math.max(f[mask[u]], h[u]);
			for(Edge e : ke[u])
				add(e.v);
		}
		
		int batBit(int u, int j) {
			return (u | (1 << j));
		}
		
		int tatBit(int u, int j) {
			return (u & (~ (1 << j)));
		}
		
		void UpdateAns(int u, int root, MyAns ans) {
			for(int j=0; j<22; j++) {
				int nmask = batBit(mask[u], j);
				ans.getMax(h[u] + f[nmask] - 2 * h[root]);
				nmask = tatBit(mask[u], j);
				ans.getMax(h[u] + f[nmask] - 2 * h[root]);
			}
			for(Edge e : ke[u]) {
				UpdateAns(e.v, root, ans);
			}
		}
		
		void clear(int u) {
			f[mask[u]] = (int)(-1e9);
			for(Edge e : ke[u])
				clear(e.v);
		}
		
		void dfs(int u, boolean keep) {
			//System.out.println(mask[u]);
			int bigChild = -1, mChild = 0;
			for(Edge e : ke[u]) {
				if (sz[e.v] > mChild) {
					bigChild = e.v;
					mChild = sz[e.v];
				}
			}
			for(Edge e : ke[u]) {
				if (e.v != bigChild)
					dfs(e.v, false);
			}
			if (bigChild != -1) {
				dfs(bigChild, true);
			}
			MyAns res = new MyAns((int)(-1e9));
			for(Edge e : ke[u]) 
			if (e.v != bigChild) {
				UpdateAns(e.v, u, res);
				add(e.v);
			}
			f[mask[u]] = Math.max(f[mask[u]], h[u]);
			for(int j=0; j<22; j++) {
				int nmask = batBit(mask[u], j);
				res.getMax(f[nmask] - h[u]);
				nmask = tatBit(mask[u], j);
				res.getMax(f[nmask] - h[u]);
			}
			kq[u] = res.res;
			for(Edge e : ke[u]) 
				kq[u] = Math.max(kq[u], kq[e.v]);
			if (!keep)
				clear(u);
		}
	}
	
	static class InputReader {
		BufferedReader reader;
		StringTokenizer tokenizer;
		
		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}
		
		public InputReader(File f) {
			try {
				reader = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				throw new RuntimeException(e);
			}
		}
		
		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 readInt() {
			return Integer.parseInt(next());
		}
		
		public long readLong() {
			return Long.parseLong(next());
		}
		
		public double readDouble() {
			return Double.parseDouble(next());
		}
		
		String readln() {
			String s = "";
			try {
				s = reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
			return s;
		}
	}
}