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.*;
import java.io.*;
/*
6
0 1 1 0 4 4
1
2 1


24
0 1 1 1 2 3 3 3 4 5 6 6 7 7 8 9 9 12 14 15 0 21 22 23
1
12 2

 */
public class BloodCousins {
	static int dfsid;
	static int[] start,end,depths;
	static ArrayList<ArrayList<Integer>> sibs;
	static ArrayList<Integer>[] children;
	public static void main(String[] args) {
		FastScanner in = new FastScanner(System.in);
		int n = in.nextInt();
		int log = 1;
		while((n >> log) > 0){
			log++;
		}
		int[][] P =  new int[log][n];
		children = new ArrayList[n];
		for (int i = 0; i < children.length; i++) {
			children[i] = new ArrayList<>();
		}
		
		for(int i =0; i < n; i++){
			P[0][i] = in.nextInt()-1;
			if(P[0][i] != -1){
				children[P[0][i]].add(i);
			}
		}
		
		for(int l = 1; l < log; l++){
			for(int i =0;i <n; i++){
				if(P[l-1][i] == -1) P[l][i] = -1;
				else P[l][i] = P[l-1][P[l-1][i]];
			}
		}
		
		dfsid = 0;
		start = new int[n];
		end = new int[n];
		depths = new int[n];
		sibs = new ArrayList<>();
		for(int i =0; i < n; i++){
			if(P[0][i] == -1){
				dfs(i,0);
			}
		}
		
		int[][] S = new int[log][n];
		for(ArrayList<Integer> level : sibs){
			for(int i =0;i < level.size()-1; i++){
				S[0][level.get(i)] = level.get(i+1);
			}
			S[0][level.get(level.size()-1)] = 987654321;
		}
		
		for(int l = 1; l < log; l++){
			for(int i =0;i <n; i++){
				if(S[l-1][i] == 987654321) S[l][i] = 987654321;
				else S[l][i] = S[l-1][S[l-1][i]];
			}
		}
		
		
		int m = in.nextInt();
		StringBuilder ans = new StringBuilder();
		
		while(m-->0){
			int v = in.nextInt()-1;
			int p = in.nextInt();
			
			int kthpar = getKthPar(P,v,p);
			
			//System.out.println("v: " + v + " p: " + p + " kthpar: " + kthpar);
			
			if(kthpar == -1){
				ans.append("0 ");
				continue;
			}
			
			//System.out.println(sibs.get(depths[v]) + " start: "  +start[kthpar] + " end: " + end[kthpar]);
			
			int j1 =getjump(S,sibs.get(depths[v]).get(0),start[kthpar],true);
			int j2 =getjump(S,sibs.get(depths[v]).get(0),end[kthpar],false);
			
			//System.out.println("j1: " + j1 + " j2: " + j2 + " diff: " + (j2-j1));
			
			ans.append((j2-j1)+" ");
			
		}
		System.out.println(ans.toString().trim());
		
	}
	
	static int getKthPar(int[][] P, int start, int k){
		if(k == 0) return start;
		int at = start;
		for(int pow2 = P.length-1; pow2 >= 0 && at != -1; pow2--){
			if((1<<pow2) < k){
				at= P[pow2][at];
				k -= (1<<pow2);
			}
		}
		
		return at == -1 ? -1 : P[0][at];
	}
	
	static int getjump(int[][] S, int start, int look, boolean isfirst){
		if(start >= look) return 0;
		int at = start;
		int ret = 0;
		for(int pow2 = S.length-1; pow2 >= 0; pow2--){
			int peek = S[pow2][at];
			if(peek < look){
				at= S[pow2][at];
				ret += (1<<pow2);
			}
		}
		
		if(at < look){
			if(isfirst)
				ret++;
			else if(S[0][at] <= look) ret++;
		}
		
		return ret;
	}
	
	static void dfs(int at, int depth){
		start[at] = dfsid++;
		depths[at] = depth;
		
		if(sibs.size() == depth) sibs.add(new ArrayList<Integer>());
		sibs.get(depth).add(start[at]);
		
		for(int c : children[at]) dfs(c, depth+1);
		
		end[at] = dfsid-1;
	}
	
	static class FastScanner{
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream in){
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer("");
		}
		
		public String next(){
			while(!st.hasMoreTokens()){
				try{
				st = new StringTokenizer(br.readLine());
				}catch(IOException e){}
			}
			return st.nextToken();
		}
		
		public int nextInt(){
			return Integer.parseInt(next());
		}
	}

}