p6pou猜到作业题是原题，可惜题面被nodgd改了，搜不出来。为了查找出处，p6pou需要提取问题描述中的关键句子。

题面可以视为一个 \(n\) 个节点的有根树，根节点是 $1$ ，每个子树都是这道作业题的子问题，共有 \(n\) 个不同的子问题。

题面中，每条边上有一个字，每条路径就是一个句子。不是所有句子都是关键句子，只有当把这个句子上所有字重新排列可以形成回文（即正着读和反着读完全相同）时，这个句子才是关键句子。特别的，没有字的句子也是关键句子，但句子字数越多就余越关键。

p6pou发现每个子问题自己都搞不定，一脸生无可恋。

p6pou决定对每个子问题都找出最关键的句子，然后去查找出处。那么，每个子问题能找出的最关键的句子有多少个字呢？

第一行一个整数 \(n\) 。
接下来 \(n-1\) 行，每行一个整数 \(p_i\) 和一个小写字母 \(c_i\) （ $2\leq i\leq n$ ），表示 \(i\) 节点的父亲节点编号和这条边上的字。

输出一行 \(n\) 个整数答案，第 \(i\) 个数是 \(i\) 子树的答案。

样例1

样例输入

4
1 s
2 a
3 s

样例输出

3 1 1 0

样例2

样例输入

5
1 a
2 h
1 a
4 h

样例输出

4 1 0 1 0

数据范围

对于20%的数据， \(n\leq 200\) ；
对于40%的数据， \(n\leq 2000\) ；
对于另外10%的数据，树高 \(\leq 30\) ；
对于另外10%的数据， $c_i\in \{\texttt{a,b}\} $ ；
对于100%的数据， $1\leq n\leq 5\times 10^5$ ， $c_i\in\{\texttt{a-v}\} $ （即共22种可能的字符）。