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, last, 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]);
		
//		System.out.println(names[3]);
//		System.out.println(names[4]);
//		System.out.println(names[6]);
//		System.out.println(names[7]);
		
		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));
		}
		
//		System.out.println(Is[1]);
		
		tree = new int[N + 10];
		last = new int[N + 10];
		Arrays.fill(last, N + 5);
		for(int l = 0; l < 2 * N + 10; l++){
//			if(l == 2)System.out.println("Is: " + Is[l] + ", " + Is[l].size());
			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;
			}
			
//			if(l == 2)System.out.println("Ls: " + Ls[l]);
			int[] a = new int[Ls[l].size()];
		
			for(int i = a.length - 1; i >= 0; i--){
				a[i] = last[nameV[Ls[l].get(i)]];
				last[nameV[Ls[l].get(i)]] = i;
			}
//			if(l == 2)System.out.println("a: " + Arrays.toString(a));
			
			Collections.sort(Is[l], new Comparator<I>() {
				@Override
				public int compare(I a, I b) {
					if(a.L < b.L)return -1;
					else return 1;
				}
			});	
			
//			if(l == 2)System.out.println("Is: " + Is[l] + ", " + Is[l].size());
			
			int ptr = Is[l].size() - 1;
			for(int L = a.length - 1; L >= 0; L--){
				update(a[L], 1);
				while(ptr >= 0 && Is[l].get(ptr).Li == L){
//					if(l == 2)System.out.println("ptr: " + ptr);
//					if(l == 2)System.out.println(get(N + 5) - get(Is[l].get(ptr).Ri) + ", " + (a.length - 1 - Is[l].get(ptr).Ri));
					if(Is[l].get(ptr).L <= Ls[l].get(Is[l].get(ptr).Li) && Ls[l].get(Is[l].get(ptr).Ri) <= Is[l].get(ptr).R && Ls[l].get(Is[l].get(ptr).Li) <= Ls[l].get(Is[l].get(ptr).Ri))
						RET[Is[l].get(ptr).i] = Is[l].get(ptr).Ri - Is[l].get(ptr).Li + 1 - get(Is[l].get(ptr).Ri);
					ptr--;
				}
			}
			
			
			for(int L = a.length - 1; L >= 0; L--)
				update(a[L], -1);
			
			for(int i = a.length - 1; i >= 0; i--)
				last[nameV[Ls[l].get(i)]] = N + 5;
		}
		
		for(int x = 0; x < Q; x++)
			out.println(RET[x]);
		out.close();
		
	}
	private static int get(int i) {
		int ret = 0;
		while(i > 0){
			ret += tree[i];
			i -= i & -i;
		}
		return ret;
	}
	private static void update(int i, int v) {
		while(i < tree.length){
			tree[i] += v;
			i += i & -i;
		}
	}
	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());
		}
	}
}