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.*;
import java.lang.Math;
import java.util.*;

public class Main
{	
	public BufferedReader in;
	public PrintStream out;
	
	public boolean log_enabled = false;
	
	int n;
	int[] P;
	int[] S,F,D;
	int[] first, last;
	int time;
	
	int[] adj_list;
	int[] adj_pos;
	int[] adj_count;
	
	int[] n_order;
	int[] order_n;
	
	public void dfs(int k, int d)
	{
		D[k] = d;
		S[k] = time++;
		
		for (int i=adj_pos[k]; i<adj_pos[k] + adj_count[k]; i++)
		{
			dfs(adj_list[i], d+1);
		}
		F[k] = time++;
	}
	
	public void test()
	{
		n = readInt();
		P = new int[n+1];
		
		adj_count = new int[n+1];
		adj_pos = new int[n+1];
		adj_list = new int[n+1];
		
		Arrays.fill(adj_count, 0);
		
		int i,j;
		for (i=1; i<=n; i++)
		{
			P[i] = readInt();
			adj_count[P[i]]++;
		}
		
		int pos = 0;
		for (i=0; i<=n; i++)
		{
			adj_pos[i] = pos;
			pos += adj_count[i];
		}
		
		Arrays.fill(adj_count, 0);
		for (i=1; i<=n; i++)
		{
			adj_list[adj_pos[P[i]]+adj_count[P[i]]++] = i;
		}
		
		S = new int[n+1];
		F = new int[n+1];
		D = new int[n+1];
		
		time = 0;
		dfs(0,0);
		
		n_order = new int[n+1];
		order_n = new int[n+1];
		
		first = new int[n+1];
		last = new int[n+1];
		
		int[] qb, q = new int[n+1], q2 = new int[n+1];
		int q_size2, q_size = 1;
		q[0] = 0;
		pos=0;
		
		int d=0;
		
		while (q_size>0)
		{	
			first[d] = pos;
			
			q_size2 = 0;
			for (i=0; i<q_size; i++)
			{
				n_order[q[i]] = pos;
				order_n[pos] = q[i];
				pos++;
				
				for (j=adj_pos[q[i]]; j<adj_pos[q[i]]+adj_count[q[i]]; j++)
				{
					q2[q_size2++] = adj_list[j];
				}
			}
			
			last[d++] = pos-1;
			
			qb = q; q = q2; q2 = qb;
			q_size = q_size2;
		}
		
		int m = readInt(), v, u, l, r, x, s, f;
		for (i=0; i<m; i++)
		{
			if (i>0) out.print(" ");
			
			v = readInt();
			d = readInt();
			
			if (D[v]<=d)
			{
				out.print(0);
				logWrite("\n");
				continue;
			}
			
			l = first[D[v]-d];
			r = last[D[v]-d];
			
			while (l<r)
			{
				x = (l+r)/2;
				if (F[order_n[x]]<S[v])
				{
					l = x+1;
				}
				else if (S[order_n[x]]>S[v])
				{
					r = x-1;
				}
				else
				{
					l=r=x;
				}
			}
			
			u = order_n[l];
			logWrite("\nu: %d\n", u);
			
			l = first[D[v]];
			r = n_order[v];
			
			while (l<r)
			{
				x = (l+r)/2;
				
				if (S[order_n[x]]<S[u])
				{
					l = x+1;
				}
				else
				{
					r = x;
				}
			}
			s = l;
			
			l = n_order[v];
			r = last[D[v]];
			
			//logWrite(" <%d  - %d> \n", l,r);
			
			while (l<r)
			{
				x = (l+r+1)/2;
				
				if (S[order_n[x]]>F[u])
				{
					r = x-1;
				}
				else
				{
					l = x;
				}
			}
			f = l;
			
			logWrite(" => %d - %d \n", s,f);
			
			out.print(f-s);
			logWrite("\n");
		}
		
		out.println();
		
	}
    
	public void run()
	{
		try
		{
			in = new BufferedReader(new InputStreamReader(System.in));
			out = System.out;
			
			//in = new BufferedReader(new FileReader("in.txt"));
			//out = new PrintStream(new File("out.txt"));
			
			
		}
		catch (Exception e)
		{
			return;
		}
		
		//while (true)
		{
			//int t = readInt(); for (int i=0; i<t; i++)					
			{
				test();
			}
		}
	}
	
	public static void main(String args[])
	{
		new Main().run();
	}
	
	private StringTokenizer tokenizer = null;
	
	public int readInt() 
	{
        return Integer.parseInt(readToken());
    }
   
    public long readLong() 
	{
        return Long.parseLong(readToken());
    }
   
    public double readDouble() 
	{
        return Double.parseDouble(readToken());
    }
   
	public String readLn()
	{	
		try
		{
			String s;
			while ((s = in.readLine()).length()==0);
			return s;
		}
		catch (Exception e)
		{
			return "";
		}
	}
	
    public String readToken() 
	{
		try
		{
			while (tokenizer == null || !tokenizer.hasMoreTokens()) 
			{
				tokenizer = new StringTokenizer(in.readLine());
			}
			return tokenizer.nextToken();
		}
		catch (Exception e)
		{
			return "";
		}
    }
	
	public int[] readIntArray(int n)
	{
		int[] x = new int[n];
		readIntArray(x, n);
		return x;
	}
	
	public void readIntArray(int[] x, int n)
	{
		for (int i=0; i<n; i++)
		{
			x[i] = readInt();
		}
	}
	
	public void logWrite(String format, Object... args)
	{
		if (!log_enabled)
		{
			return;
		}
		
		out.printf(format, args);
	}
}