You are given a rooted tree that contains N nodes. Each node contains a lowercase alphabet.
You are required to answer Q queries of type u,c, where u is an integer and c is a lowercase alphabet. The count of nodes in the subtree of the node u containing c is considered as the answer of all the queries.
Input format
Output format
For each query, print the output in a new line.
Constraints
1≤N,Q≤1051≤u,v≤N
Note: It is guaranteed that the input generates a valid tree.
Tree given in the sample input will look like that.
Number of nodes in the subtree of node 1 having 'a' stored in it is 2.