Problem: Polycarpus got hold of a family tree. The found tree describes the family relations of n people, numbered from 1 to n. Every person in this tree has at most one direct ancestor. Also, each person in the tree has a name, the names are not necessarily unique.

We call the man with a number a a 1-ancestor of the man with a number b, if the man with a number a is a direct ancestor of the man with a number b.

We call the man with a number a a k-ancestor (k > 1) of the man with a number b, if the man with a number b has a 1-ancestor, and the man with a number a is a (k - 1)-ancestor of the 1-ancestor of the man with a number b.

In the tree the family ties do not form cycles. In other words there isn't a person who is his own direct or indirect ancestor (that is, who is an x-ancestor of himself, for some x, x > 0).

We call a man with a number a the k-son of the man with a number b, if the man with a number b is a k-ancestor of the man with a number a.

Polycarpus is very much interested in how many sons and which sons each person has. He took a piece of paper and wrote m pairs of numbers vi, ki. Help him to learn for each pair vi, ki the number of distinct names among all names of the ki-sons of the man with number vi.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 105) — the number of people in the tree. Next n lines contain the description of people in the tree. The i-th line contains space-separated string si and integer ri (0 ≤ ri ≤ n), where si is the name of the man with a number i, and ri is either the number of the direct ancestor of the man with a number i or 0, if the man with a number i has no direct ancestor. 

The next line contains a single integer m (1 ≤ m ≤ 105) — the number of Polycarpus's records. Next m lines contain space-separated pairs of integers. The i-th line contains integers vi, ki (1 ≤ vi, ki ≤ n).

It is guaranteed that the family relationships do not form cycles. The names of all people are non-empty strings, consisting of no more than 20 lowercase English letters.

Output

Print m whitespace-separated integers — the answers to Polycarpus's records. Print the answers to the records in the order, in which the records occur in the input.

Examples

Input

6
pasha 0
gerald 1
gerald 1
valera 2
igor 3
olesya 1
5
1 1
1 2
1 3
3 1
6 1


Output

2
2
0
1
0


Input

6
valera 0
valera 1
valera 1
gerald 0
valera 4
kolya 4
7
1 1
1 2
2 1
2 2
4 1
5 1
6 1


Output

1
0
0
0
2
0
0

Solution (in JAVA):

Solution:
import java.util.*;
public class E {
	static String[] N;
	static int[] P;
	
	static int[] DEPTH;
	static int[] START;
	static int[] FINISH;
	static List<List<Integer>> C = new ArrayList<List<Integer>>();
	static int t;
	static void dfs(int x, int d) {
		DEPTH[x] = d;
		START[x] = t++;
		for(Integer c:C.get(x))
			dfs(c, d+1);
		FINISH[x] = t++;
	}
	static Set<String> single(String S) {
		Set<String> ret = new HashSet<String>();
		ret.add(S);
		return ret;
	}
	static Set<String> union(Set<String> A, Set<String> B) {
		if(A.size() < B.size()) { B.addAll(A); return B; }
		else { A.addAll(B); return A; }
	}
	public static void main(String[] args) {
		new Thread(null, new Runnable() {
            public void run() {
        		Scanner in = new Scanner(System.in);
        		int n = in.nextInt();
        		for(int i=0; i<n; i++) C.add(new ArrayList<Integer>());
        		N = new String[n];
        		P = new int[n];
        		DEPTH = new int[n];
        		START = new int[n];
        		FINISH = new int[n];
        		List<Integer> roots = new ArrayList<Integer>();
        		for(int i=0; i<n; i++) { 
        			N[i] = in.next();
        			P[i] = in.nextInt()-1;
        			if(P[i] == -1) roots.add(i);
        			else C.get(P[i]).add(i);
        		}
        		t = 0;
        		for(Integer root:roots)
        			dfs(root, 0);
        		
        		int Q = in.nextInt();
        		int[][] Qs = new int[Q][4];
        		int[] A = new int[Q];
        		for(int i=0; i<Q; i++) {
        			int v = in.nextInt()-1;
        			int k = in.nextInt();
        			Qs[i] = new int[]{DEPTH[v]+k, START[v], FINISH[v], i};
        		}
        		List<TreeMap<Integer, Set<String>>> Ds = new ArrayList<TreeMap<Integer, Set<String>>>();
        		for(int i=0; i<=n; i++) Ds.add(new TreeMap<Integer, Set<String>>());
        		for(int i=0; i<n; i++) Ds.get(DEPTH[i]).put(START[i], single(N[i]));
        		
        		Arrays.sort(Qs, new Comparator<int[]>() {
        			public int compare(int[] A, int[] B) {
        				if(A[0] != B[0]) return A[0]-B[0];
        				int la = A[2]-A[1];
        				int lb = B[2]-B[1];
        				if(la != lb) return la-lb;
        				return A[3]-B[3];
        			}
        		});
        		
        		for(int i=0; i<Q; i++) {
        			if(Qs[i][0] >= Ds.size()) { A[Qs[i][3]] = 0; continue; }
        			TreeMap<Integer, Set<String>> M = Ds.get(Qs[i][0]);
        			Integer k = M.ceilingKey(Qs[i][1]);
        			//System.out.println(Qs[i][1]+" "+Qs[i][2]+" "+M);
        			if(k==null || k>Qs[i][2]) { A[Qs[i][3]] = 0; continue; }
        			while(true) {
        				Integer k2 = M.higherKey(k);
        				if(k2 == null || k2>Qs[i][2]) break;
        				M.put(k, union(M.get(k), M.get(k2)));
        				M.remove(k2);
        			}
        			A[Qs[i][3]] = M.get(k).size();
        		}
        		
        		for(int i=0; i<Q; i++)
        			System.out.println(A[i]);
            }
        }, "1", 1 << 23).start();
	}
}