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 t208 {
	int n;
	int [] parent;
	int [] child_count;
	int [][] child;
	int [][] par2;
	boolean [] visited;
	int [] dfsno;
	int dfsi = 0;
	Vector [] nodesByLevel;
	int [] level;
	Scanner in = new Scanner(System.in);
	int [] cnt;
	public void readin(){
		n = in.nextInt();
		parent = new int[n+1];
		child = new int[n+1][];
		child_count = new int[n+1];
		par2 = new int[n+1][17];
		visited = new boolean[n+1];
		dfsno = new int[n+1];
		nodesByLevel = new Vector[n+1];
		level = new int[n+1];
		cnt = new int[n+1];
		for(int i = 1; i <= n; ++i){
			parent[i] = in.nextInt();
			child_count[parent[i]]++;
			par2[i][0] = parent[i];
			nodesByLevel[i-1] = new Vector();
		}
		for(int i = 1; i <= n; ++i){
			child[i] = new int[child_count[i]];
			child_count[i] = 0;
		}
		for(int i = 1; i <= n; ++i){
			if(parent[i] > 0)
				child[parent[i]][child_count[parent[i]]++] = i;
		}
		
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j < 17; ++j){
				par2[i][j] = par2[par2[i][j-1]][j-1];
			}
		}
		
	}
	public int kthParent(int v, int k){
		int j = 0;
		while(k != 0){
			if((k & 1) == 1) v = par2[v][j];
			k >>= 1;
			j++;
		}
		return v;
	}
	void dfs(int v){
		visited[v] = true;
		dfsno[v] = ++dfsi;
		nodesByLevel[level[v]].add(dfsi);
		cnt[v] = 1;
		for(int c : child[v]){
			if(!visited[c]){
				level[c] = level[v] + 1;
				dfs(c);
				cnt[v] += cnt[c];
			}
		}
	}
	int lowerBound(Vector v, int key){
		int low = 0;
		int high = v.size();
		while(low < high){
			int m = (low + high) / 2;
			if(key <= (Integer)v.get(m)) 
				high = m;
			else
				low = m + 1;
		}
		return low;
	}
	int higherBound(Vector v, int key){
		int low = 0;
		int high = v.size();
		while(low < high){
			int m = (low + high) / 2;
//			System.out.println("low="+low+",hi="+high+",mid=" +m+",v[mid]=" + v.get(m));
			if(key < (Integer)v.get(m)) 
				high = m;
			else
				low = m + 1;
		}
		return low;
	}
	public void solve(){
		readin();
		int k = in.nextInt();
		int v, p, u;
		for(int i = 1; i <= n; ++i)
			if(!visited[i]) dfs(i);

		for(int i = 0; i < k; ++i){
			v = in.nextInt();
			p = in.nextInt();
			u = kthParent(v, p);
//			System.out.println("u="+u);
//		for(Object c : nodesByLevel[level[v]]) System.out.print(c + " "); System.out.println();
//			System.out.println("hb " + cnt[u]);
//			System.err.println(v + "," + p);
			int tot = ((higherBound(nodesByLevel[level[v]], dfsno[u] + cnt[u]) - lowerBound(nodesByLevel[level[v]], dfsno[u])-1));
			tot = Math.max(tot, 0);
			System.out.println(tot + " ");
			
		}
		System.out.println();
	}
	public static void main(String[] args){
		new t208().solve();
	}
}