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.BufferedInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

public class Main
{	
	private int n;
	private int cnt;
	private int[] pa;
	private int[] head;
	private ArrayList<Edge> edge;
	private int[] depth;
	private int[] index;
	private ArrayList<ArrayList<Integer>> layer;
	
	public void addEdge(int u, int v)
	{
		edge.add(new Edge(v, head[u]));
		head[u] = cnt++;
	}
	
	public void dfs(int u, int d)
	{
		depth[u] = d;
		index[u] = cnt;
		if(d >= layer.size())
		{
			layer.add(new ArrayList<Integer>());
		}
		layer.get(d).add(cnt);
		++cnt;
		for(int i = head[u];i != -1;i = edge.get(i).next)
		{
			int v = edge.get(i).v;
			dfs(v, d + 1);
		}
	}
	
	public void foo()
	{
		MyScanner scan = new MyScanner();
		n = scan.nextInt();
		pa = new int[n + 1];
		head = new int[n + 1];
		Arrays.fill(head, -1);
		cnt = 0;
		edge = new ArrayList<Edge>();
		for(int i = 1;i <= n;++i)
		{
			pa[i] = scan.nextInt();
			if(pa[i] != 0)
			{
				addEdge(pa[i], i);
			}
		}
		cnt = 0;
		depth = new int[n + 1];
		index = new int[n + 1];
		layer = new ArrayList<ArrayList<Integer>>();
		for(int i = 1;i <= n;++i)
		{
			if(0 == pa[i])
			{
				dfs(i, 0);
			}
		}
		int m = scan.nextInt();
		while(m-- > 0)
		{
			int v = scan.nextInt();
			int p = scan.nextInt();
			int d = depth[v];
			if(d < p)
			{
				System.out.println(0);
			}
			else
			{
				int dParent = d - p;
				ArrayList<Integer> arr = layer.get(d);
				ArrayList<Integer> arrParent = layer.get(dParent);
				int posParent = -Collections.binarySearch(arrParent, index[v]) - 2;
				int indexParent = arrParent.get(posParent);
				int leftIndex = -Collections.binarySearch(arr, indexParent) - 1;
				int rightIndex = arr.size() - 1;
				if(posParent < arrParent.size() - 1)
				{
					rightIndex = -Collections.binarySearch(arr, arrParent.get(posParent + 1)) - 2;
				}
				System.out.println(rightIndex - leftIndex);
			}
		}
	}
	
	public static void main(String[] args)
	{
		new Main().foo();
	}
	
	class Edge
	{
		private int v;
		private int next;
		public Edge(int aV, int aNext)
		{
			v = aV;
			next = aNext;
		}
	}
	
	class MyScanner
	{
	    private byte[] buf = new byte[1024];
	    private int curChar;
	    private int numChars;
	    BufferedInputStream bis = new BufferedInputStream(System.in);

	    public int read() 
	    {
	        if (-1 == numChars)
	        {
	        	throw new InputMismatchException();
	        }
	        if (curChar >= numChars)
	        {
	            curChar = 0;
	            try 
	            {
	                numChars = bis.read(buf);
	            }
	            catch (IOException e)
	            {
	                throw new InputMismatchException();
	            }
	            if (numChars <= 0)
	            {
	            	return -1;
	            }
	        }
	        return buf[curChar++];
	    }

	    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 String next()
	    {
	        int c = read();
	        while (isSpaceChar(c))
	        {
	        	c = read();
	        }
	        StringBuilder res = new StringBuilder();
	        do 
	        {
	            res.appendCodePoint(c);
	            c = read();
	        } while (!isSpaceChar(c));
	        return res.toString();
	    }

	    private boolean isSpaceChar(int c) 
	    {
	        return ' ' == c || '\n' == c || '\r' == c || '\t' == c || -1 == c;
	    }
	}
}