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.Collections;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.TreeMap;
						public class Main implements Runnable
						{
							static final long MOD = 1000000007L;
							static final long MOD2 = 1000000009L;
							static class InputReader
							{
								private InputStream stream;
								private byte[] buf = new byte[1024];
								private int curChar;
								private int numChars;
								private SpaceCharFilter filter;
								private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
						 
								public InputReader(InputStream stream)
								{
									this.stream = stream;
								}
								
								public int read()
								{
									if (numChars==-1) 
										throw new InputMismatchException();
									
									if (curChar >= numChars)
									{
										curChar = 0;
										try 
										{
											numChars = stream.read(buf);
										}
										catch (IOException e)
										{
											throw new InputMismatchException();
										}
										
										if(numChars <= 0)				
											return -1;
									}
									return buf[curChar++];
								}
							 
								public String nextLine()
								{
									String str = "";
						            try
						            {
						                str = br.readLine();
						            }
						            catch (IOException e)
						            {
						                e.printStackTrace();
						            }
						            return str;
								}
								public int nextInt()
								{
									int c = read();
									
									while(isSpaceChar(c)) 
										c = read();
									
									int sgn = 1;
									
									if (c == '-') 
									{
										sgn = -1;
										c = read();
									}
									
									int res = 0;
									do 
									{
										if(c<'0'||c>'9') 
											throw new InputMismatchException();
										res *= 10;
										res += c - '0';
										c = read();
									}
									while (!isSpaceChar(c)); 
									
									return res * sgn;
								}
								
								public long nextLong() 
								{
									int c = read();
									while (isSpaceChar(c))
										c = read();
									int sgn = 1;
									if (c == '-') 
									{
										sgn = -1;
										c = read();
									}
									long res = 0;
									
									do 
									{
										if (c < '0' || c > '9')
											throw new InputMismatchException();
										res *= 10;
										res += c - '0';
										c = read();
									}
									while (!isSpaceChar(c));
										return res * sgn;
								}
								
								public double nextDouble() 
								{
									int c = read();
									while (isSpaceChar(c))
										c = read();
									int sgn = 1;
									if (c == '-') 
									{
										sgn = -1;
										c = read();
									}
									double res = 0;
									while (!isSpaceChar(c) && c != '.') 
									{
										if (c == 'e' || c == 'E')
											return res * Math.pow(10, nextInt());
										if (c < '0' || c > '9')
											throw new InputMismatchException();
										res *= 10;
										res += c - '0';
										c = read();
									}
									if (c == '.') 
									{
										c = read();
										double m = 1;
										while (!isSpaceChar(c)) 
										{
											if (c == 'e' || c == 'E')
												return res * Math.pow(10, nextInt());
											if (c < '0' || c > '9')
												throw new InputMismatchException();
											m /= 10;
											res += (c - '0') * m;
											c = read();
										}
									}
									return res * sgn;
								}
								
								public String readString() 
								{
									int c = read();
									while (isSpaceChar(c))
										c = read();
									StringBuilder res = new StringBuilder();
									do 
									{
										res.appendCodePoint(c);
										c = read();
									} 
									while (!isSpaceChar(c));
									
									return res.toString();
								}
							 
								public boolean isSpaceChar(int c) 
								{
									if (filter != null)
										return filter.isSpaceChar(c);
									return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
								}
							 
								public String next() 
								{
									return readString();
								}
								
								public interface SpaceCharFilter 
								{
									public boolean isSpaceChar(int ch);
								}
							}
						 	
							public static void main(String args[]) throws Exception
							{
								new Thread(null, new Main(),"Main",1<<26).start();
							}
							int MAXN = 1000001;
							ArrayList<Integer> adj[];

							
							int[] dx = {1,-1,0,0};
							int[] dy = {0,0,1,-1};
							public void run() 
							{
								
									//InputReader sc= new InputReader(new FileInputStream("input.txt"));
									//PrintWriter w= new PrintWriter(new FileWriter("output.txt"));
									InputReader sc = new InputReader(System.in);
                                    PrintWriter w = new PrintWriter(System.out);
                		            int n = sc.nextInt();
                		            start = new int[n+1];
                		            end=  new int[n+1];
                		            depth = new int[n+1];
                		            parent = new int[n+1][21];
                		            adj = new ArrayList[n+1];
                		            for(int i = 1;i <= n;i++) {
                		            	adj[i] = new ArrayList();
                		            }
                		            for(int i = 1;i <= n;i++) {
                		            	int x = sc.nextInt();
                		            	if(x == 0) {
                		            		parent[i][0] = 0;
                		            		continue;
                		            	}else {
                		            		parent[i][0] = x;
                		            	}
                		            	adj[i].add(x);
                		            	adj[x].add(i);
                		            }
                		            for(int i = 1;i <= n;i++) {
                		            	if(parent[i][0] == 0) {
                		            		dfs(i,0,0);
                		            	}
                		            }
                		            for(int j = 1;j <= 20;j++) {
                		            	for(int i = 1;i <= n;i++) {
                		            		if(parent[i][j-1] != -1) {
                		            			parent[i][j] = parent[parent[i][j-1]][j-1];
                		            		}
                		            	}
                		            }
                		            TreeMap<Integer,ArrayList<Integer>> tmap = new TreeMap();
                		            for(int i = 1;i <= n;i++) {
                		            	if(!tmap.containsKey(depth[i])) {
                		            		tmap.put(depth[i],new ArrayList());
                		            	}
                		            	tmap.get(depth[i]).add(start[i]);
                		            }
                		            for(Integer key: tmap.keySet()) {
                		            	Collections.sort(tmap.get(key));
                		            }
                		            int q = sc.nextInt();
                		            while(q-- > 0) {
                		            	int v = sc.nextInt();
                		            	int p = sc.nextInt();
                		            	if(depth[v] < p) {
                		            		w.print("0 ");
                		            	}else {
                		            		ArrayList<Integer> toSearch = tmap.get(depth[v]);
                		            		for(int i = 0;i < 21;i++) {
                		            			if(((p>>i) & 1) == 1) {
                		            				v = parent[v][i];
                		            			}
                		            		}
                		            		int ele = -(Collections.binarySearch(toSearch,start[v]) + 1);
                		            		int ele2 = -(Collections.binarySearch(toSearch,end[v]) + 1);
                		            		w.print(ele2-ele-1 + " ");
                		            	}
                		            }
                		            w.close();							
								
								
							}
							int[] start;
							int[] end;
							int time = 0;
							int[] depth;
							int[][] parent;
							void dfs(int curr,int prev,int dep) {
								depth[curr] = dep;
								start[curr] = time++;
								Iterator<Integer> it = adj[curr].iterator();
								while(it.hasNext()) {
									int n = it.next();
									if(n != prev) {
										dfs(n,curr,dep+1);
									}
								}
								end[curr] = time++;
							}
							static class Pair implements Comparable<Pair>{
								long a;
								long b;
								
								Pair(long a,long b){
									this.a = a;
									this.b = b;
									
								}
								@Override
								public int compareTo(Pair o) {
									// TODO Auto-generated method stub
									return Long.compare(this.a+this.b,o.a+o.b);
								}
								public boolean equals(Object o) {
									Pair p = (Pair)o;
									return this.a == p.a && this.b == p.b;
								}
								public int hashCode(){
									return Long.hashCode(a)*27 + Long.hashCode(b)* 31;
								}
							}
							
						}