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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.StringTokenizer;


public class Main {

	/**
	 * @param args
	 */
	static HashMap<String, Integer> mp;
	static int N, id = 1, inf = 1 << 28;
	static String[] names;
	static ArrayList<Integer>[] g;
	static ArrayList<Integer>[] Ls;
	static ArrayList<I>[] Is;
	static int[] P, L, M, Max, Min, tree, count, nameV;
	public static void main(String[] args) {
		InputReader r = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		N = r.nextInt();
		
		names = new String[N + 10];
		g = new ArrayList[N * 2 + 10];
		for(int i = 0; i < N * 2 + 10; i++)
			g[i] = new ArrayList<Integer>();
		Ls = new ArrayList[N * 2 + 10];
		for(int i = 0; i < N * 2 + 10; i++)
			Ls[i] = new ArrayList<Integer>();
		Is = new ArrayList[N * 2 + 10];
		for(int i = 0; i < N * 2 + 10; i++)
			Is[i] = new ArrayList<I>();
		
		nameV = new int[N + 10];
		P = new int[N + 10];
		L = new int[N + 10];
		M = new int[N + 10];
		Max = new int[N + 10];
		Min = new int[N + 10];
		
		for(int k = 1; k <= N; k++){
			names[k] = r.next();
			
			P[k] = r.nextInt();
			
			g[P[k]].add(k);
		}
		
		dfs(0, 0);
		mp = new HashMap<String, Integer>();
		int idx = 1;
		for(int i = 1; i <= N; i++)
			if(!mp.containsKey(names[i])){
				mp.put(names[i], idx);
				nameV[M[i]] = idx++;
			}else nameV[M[i]] = mp.get(names[i]);
		
		int Q = r.nextInt();
		int[] RET = new int[Q];
		
		for(int x = 0; x < Q; x++){
			int V = r.nextInt();
			int K = r.nextInt();
			
			Is[L[V] + K].add(new I(Min[V], Max[V], x));
		}
		
		tree = new int[N + 10];
		count = new int[N + 10];
		
		ArrayList<I>[] SQ = new ArrayList[1001];
		for(int i = 0; i < 1001; i++)
			SQ[i] = new ArrayList<I>();
		
		for(int l = 0; l < 2 * N + 10; l++)if(Ls[l].size() > 0){
			for(I i : Is[l]){
				int lo = 0, hi = Ls[l].size() - 1;
				while(lo < hi){
					int md = (lo + hi) / 2;
					
					if(Ls[l].get(md) >= i.L){
						hi = md;
					}else{
						lo = md + 1;
					}
				}
				i.Li = lo;
				
				lo = 0;
				hi = Ls[l].size() - 1;
				while(lo < hi){
					int md = (lo + hi + 1) / 2;
					
					if(Ls[l].get(md) <= i.R){
						lo = md;
					}else{
						hi = md - 1;
					}
				}
				i.Ri = lo;
			}
			
			Collections.sort(Is[l], new Comparator<I>() {
				@Override
				public int compare(I a, I b) {
					if(a.R < b.R)return -1;
					else return 1;
				}
			});
			
			int lo = 1, hi = Ls[l].size();
			while(lo < hi){
				int md = (lo + hi) / 2;
				if(md * md < Ls[l].size())lo = md + 1;
				else if(md * md == Ls[l].size())lo = hi = md;
				else hi = md - 1;
			}
			
			int K = lo;
			
			for(I i : Is[l])
				SQ[i.Li / K].add(i);
			
			for(int x = 0; x < Ls[l].size() / K + 10; x++){
				int L = -1, R = -1;
				int sum = 0;
				for(I i : SQ[x]){
					if(!(i.L <= Ls[l].get(i.Li) && Ls[l].get(i.Ri) <= i.R))continue;
					if(R == -1){
						L = R = i.Ri;
						count[nameV[Ls[l].get(R)]]++;
						sum = 1;
					}
					while(R < i.Ri){
						R++;
						count[nameV[Ls[l].get(R)]]++;
						if(count[nameV[Ls[l].get(R)]] == 1)sum++;
					}
					while(i.Li < L){
						L--;
						count[nameV[Ls[l].get(L)]]++;
						if(count[nameV[Ls[l].get(L)]] == 1)sum++;
					}
					while(L < i.Li){
						count[nameV[Ls[l].get(L)]]--;
						if(count[nameV[Ls[l].get(L)]] == 0)sum--;
						L++;
					}
					
					RET[i.i] = sum;
				}
				
				L = R = -1;
				for(I i : SQ[x]){
					if(!(i.L <= Ls[l].get(i.Li) && Ls[l].get(i.Ri) <= i.R))continue;
					if(R == -1){
						L = R = i.Ri;
						count[nameV[Ls[l].get(R)]] = 0;
					}
					
					while(R < i.Ri){
						R++;
						count[nameV[Ls[l].get(R)]] = 0;
					}
					
					while(i.Li < L){
						L--;
						count[nameV[Ls[l].get(L)]] = 0;
					}
					while(L < i.Li){
						count[nameV[Ls[l].get(L)]] = 0;
						L++;
					}
				}
				SQ[x].clear();
			}
		}
		
		for(int x = 0; x < Q; x++)
			out.println(RET[x]);
		out.close();
		
	}
	private static void dfs(int x, int l) {
		M[x] = id++;
		Min[x] = id;
		
		L[x] = l; 
		Ls[l].add(M[x]);
		for(int j : g[x])
			dfs(j, l + 1);
		Max[x] = id - 1;
	}
	static class I{
		int L, R, ret, i, Li, Ri;
		public I(int Li, int Ri, int ii){
			L = Li;
			R = Ri;
			i = ii;
		}
		public String toString(){
			return String.format("(%d, %d, %d: %d, %d)", L, R, i, Li, Ri);
		}
	}
	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
				return null;
			}
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public double nextDouble(){
			return Double.parseDouble(next());
		}
	}
}