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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.*;
import java.util.*;
import java.util.Map.Entry;

public class TestClass {
	private static InputStream stream;
	private static byte[] buf = new byte[1024];
	private static int curChar;
	private static int numChars;
	private static SpaceCharFilter filter;
	private static PrintWriter pw;
	
	static int n = 0,counter = 0,time = 0;
	static int parent[],root[],level[],st[],et[],p[][];
	static ArrayList<Integer> a[],b[];
	public static void dfs(int index,int lev){
		st[index] = time++;
		level[index] = lev;
		for(int i=0;i<a[index].size();i++)
			dfs(a[index].get(i),lev+1);
		et[index] = time-1;
	}
	private static void soln(){
		n = nI();
		parent  = new int[n+1];
		root = new int[n+1];
		level = new int[n+1];
		st = new int[n+1];
		et = new int[n+1];
		a = new ArrayList[n+1];
		b = new ArrayList[n+1];
		for(int i=0;i<=n;i++){
			a[i] = new ArrayList<Integer>();
			b[i] = new ArrayList<Integer>();
		}
		for(int i=1;i<=n;i++){
			parent[i] = nI();
			a[parent[i]].add(i);
			if(parent[i]==0)
				root[counter++] = i;
		}
		p = new int[n+1][(int)(Math.log10(n)/Math.log10(2))+1];
		for(int i=0;i<=n;i++)
			p[i][0] = parent[i];
		dfs(0,0);
		int dp[] = new int[25];
		dp[0] = 1;
		for(int i=1;i<25;i++)
			dp[i] = dp[i-1]*2;
		for(int j=1;dp[j]<=n;j++){
			for(int i=0;i<=n;i++)
				p[i][j] = p[p[i][j-1]][j-1];
		}
		for(int i=0;i<=n;i++)
			b[level[i]].add(st[i]);
		for(int i=0;i<=n;i++)
			Collections.sort(b[i]);
		int q = nI();
		while(q-->0){
			int x = nI(),y = nI();
			int kl = y;
			if(level[x]<=y){
				pw.print("0 ");
				continue;
			}
			int log = 0;
			for(;dp[log++]<=y;);
			log--;
			for(int i=log;i>=0;i--){
				if(y-dp[i]>0){
					x = p[x][i];
					y-=dp[i];
				}
			}
			x = parent[x];
			pw.print((bs(et[x]+1,level[x]+kl)-bs(st[x],level[x]+kl)-1)+" ");
		}
	}
	public static int bs(int index,int level){
		int x = 0,y = b[level].size()-1;
		if(b[level].get(0)>=index)
			return 0;
		while(x<y){
			int mid = (x+y)/2;
			if(b[level].get(mid)<=index)
				x = mid+1;
			else
				y = mid;
		}
		if(b[level].get(x)>=index)
			return x;
		else
			return x+1;
	}
	public static void main(String[] args) {
		InputReader(System.in);
		pw = new PrintWriter(System.out);
		soln();
		pw.close();
	}
	// To Get Input
	// Some Buffer Methods
	public static void InputReader(InputStream stream1) {
		stream = stream1;
	}
	private static boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}
	private static boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
	private static 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++];
	}
	private static int nI() {
		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;
	}
	private static long nL() {
		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;
	}
	private static String nextToken() {
		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 static String nLi() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}
	private static boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}
	private interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}