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.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class Solution{
	
	static int n;
	static ArrayList<Integer>[] g;
	static int[][] par;
	static int[] start, end;
	static int timer = 0;
	static int[] h;
	
	
    public static void main(String[] args) throws IOException {
    	
		
    	FastScanner fs = new FastScanner();
    	PrintWriter out = new PrintWriter(System.out);
    		
    	int tt = 1;
    	while(tt-->0) {

    		n = fs.nextInt();
    		g = new ArrayList[n+1];
    		for(int i=0;i<=n;i++) g[i] = new ArrayList<Integer>();
    		
    		ArrayList<Integer> roots = new ArrayList<Integer>();
    		
    		for(int i=1;i<=n;i++) {
    			int p = fs.nextInt();
    			if(p!=0) {
    				g[p].add(i);
    			}
    			else {
    				roots.add(i);
    			}
    		}
    		
    		
    		par = new int[n+1][20];
    		start = new int[n+1];
    		end = new int[n+1];
    		h = new int[n+1];
    		
    		int[][] PAR = par;
    		int[] START = start;
    		int[] END = end;
    		int[] H = h;
    		
    		for(int i: roots) {
    			dfs(i, 0, 0);
    		}
    		
    		ArrayList<Integer>[] l = new ArrayList[n+1];
    		for(int i=0;i<=n;i++) l[i] = new ArrayList<Integer>();
    		
    		for(int i=1;i<=n;i++) {
    			l[h[i]].add(start[i]);
    		}
    		
    		for(int i=0;i<=n;i++) Collections.sort(l[i]);
    		
    		int m = fs.nextInt();
    		
    		while(m-->0) {
    			int v = fs.nextInt();
    			int p = fs.nextInt();
    			
    			int u = getPar(v, p);
    			if(u==0) {
    				out.print(0+" ");
    				continue;
    			}
    			int ans = lowerbound(l[h[v]], end[u]+1) - lowerbound(l[h[v]], start[u]);
    			out.print(ans-1+" ");
    		}
    		out.println();
    		
    		
    		
    		
    		
    		
    		
    	}
    	
    	out.close();
    	
    }
    
    static int lowerbound(ArrayList<Integer> list, int k) {
    	int l = 0, r = list.size();
    	while(l<r) {
    		int mid = (l+r)/2;
    		if(list.get(mid)>=k	) {
    			r = mid;
    		}
    		else {
    			l = mid + 1;
    		}
    	}
    	return l;
    }
    
    
    static void dfs(int v, int height, int p) {
    	h[v] = height;
    	start[v] = timer++;
    	par[v][0] = p;
    	for(int j=1;j<20;j++) {
    		par[v][j] = par[par[v][j-1]][j-1];
    	}
    	for(int u: g[v]) {
    		dfs(u, height+1, v);
    	}
    	end[v] = timer-1;
    }
    
    static int getPar(int v, int k) {
    	for(int j=0;j<20;j++) {
    		if((k&(1<<j))!=0) {
    			v = par[v][j];
    		}
    	}
    	return v;
    }
    
   
    
    
    static final Random random=new Random();
    
    static <T> void shuffle(T[] arr) {
    	int n = arr.length;
    	for(int i=0;i<n;i++	) {
    		int k = random.nextInt(n);
    		T temp = arr[k]; arr[k] = arr[i]; arr[i] = temp;
    	}
    }
    
    	
    static void ruffleSort(int[] a) {
    	int n=a.length;//shuffle, then sort 
    	for (int i=0; i<n; i++) {
    		int oi=random.nextInt(n); int temp=a[oi];
    		a[oi]=a[i]; a[i]=temp;
    	}
    	Arrays.sort(a);
    }
    
    static void ruffleSort(long[] a) {
    	int n=a.length;//shuffle, then sort 
    	for (int i=0; i<n; i++) {
    		int oi=random.nextInt(n); long temp=a[oi];
    		a[oi]=a[i]; a[i]=temp;
    	}
    	Arrays.sort(a);
    }
   
  
    
    static void reverse(int[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++){
    		int temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    
    static void reverse(long[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++){
    		long temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    
    
    static <T> void reverse(T[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++) {
    		T temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    	
    	
    static class FastScanner{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer("");
     
    	public String next(){
    		while(!st.hasMoreElements()){
    			try{
    				st = new StringTokenizer(br.readLine());
    			} catch(IOException e){
    				e.printStackTrace();
    			}
    		}
    		return st.nextToken();
    	}
    		
    	public String nextLine() throws IOException {
    		return br.readLine();
    	}
    		
    	public int nextInt(){
    		return Integer.parseInt(next());
    	}
     
    	public int[] readArray(int n){
    		int[] a = new int[n];
    		for(int i=0;i<n;i++)
    			a[i] = nextInt();
    		return a;
    	}
    		
    	public long nextLong() {
    		return Long.parseLong(next());
    	}
    		
    	public char nextChar() {
    		return next().toCharArray()[0];
    	}
    }
   	
}