Once Konstantin, having participated in the next, already the 13th international Olympiad, was returning home by train. He, as always, sat and thought about the meaning of life, simultaneously solving programming problems. After some time, Konstantin dozed off, but the trouble is, in order to wake up, he must solve the problem that has popped up in his head, which haunts him!
This time, Konstantin dreamed of a tree that initially consisted of only one vertex with number 1. In the problem he set, new vertices were gradually added to the tree. In the i-th second, a vertex with the number i+1 was added to the tree, which was suspended as a son from the vertex p
i, and on the edge between the vertices i+1 and p
i the letter c
i was written.
Each path from the root of the tree to the vertex v corresponds to a certain string obtained by writing out the symbols written on the edges of the current path in the order from the root to the vertex v. Konstantin faced a difficult task at first glance - after each addition of a new vertex, count the number of unique strings starting at the root of the tree (vertex number 1) and ending at some other vertex.
In his dream, Konstantin is not a genius at all, so he himself cannot solve this problem. Help Konstantin solve the problem and wake up.
Input:
The first line contains the number n - the number of requests to add a new node to the tree (1 <= n <= 300000).
The next n lines describe requests for adding vertices. The i-th query is described by the parameters p
i (1 <= p
i <= i) and c
i, which mean that the added the vertex with number i+1 is suspended from the vertex with number p
i as a child, and the symbol c
i is written on the resulting edge - a lowercase letter of the Latin alphabet.
Output:
Print n lines. On the i-th line print the answer to Konstantin's problem after adding the i+1-th vertex.
Examples:
| Input |
Output |
2
1 b
2p |
1
2 |
3
1 o
1 o
2 j |
1
1
2 |