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

public class A implements Runnable {
	BufferedReader in;
	static PrintWriter out;
	StringTokenizer st;
	Random rnd;
	
	class Query {
		int id, distance;
		int history;

		public Query(int id, int distance) {
			this.id = id;
			this.distance = distance;
		}
	}
	
	List<Integer>[] g;
	List<Query>[] firstQueries;
	List<Query>[] secondQueries;
	int[] ans, totalByDepth;
	List<Integer> stack;
	
	void firstDfs(int u) {
		
		for(Query q : firstQueries[u]) {
			if(q.distance < stack.size()) {
				int needVertex = stack.get(stack.size() - q.distance);
				secondQueries[needVertex].add(new Query(q.id, q.distance));
			}
		}
		

		stack.add(u);
		
		for(int v : g[u]) {
			firstDfs(v);
		}
		
		stack.remove(stack.size() - 1);
	}
	
	void secondDfs(int u, int level) {
		totalByDepth[level]++;
		
		for(Query q : secondQueries[u]) {
			q.history = totalByDepth[level + q.distance];
		}
		
		for(int v : g[u]) {
			secondDfs(v, level + 1);
		}
		
		
		for(Query q : secondQueries[u]) {
			ans[q.id] = totalByDepth[level + q.distance] - q.history - 1;
		}
	}
	
	void solve() throws IOException {
		int n = nextInt();
		
		g = new LinkedList[n + 1];
		firstQueries = new LinkedList[n + 1];
		secondQueries = new LinkedList[n + 1];
		stack = new ArrayList<Integer>();
		totalByDepth = new int[n + 1];
		
		for(int i = 0; i <= n; i++) {
			g[i] = new LinkedList<Integer>();
			firstQueries[i] = new LinkedList<Query>();
			secondQueries[i] = new LinkedList<Query>();
		}
		
		for(int i = 1; i <= n; i++) {
			int parent = nextInt();
			g[parent].add(i);
		}
		
		int m = nextInt();
		
		ans = new int[m];
		
		for(int i = 0; i < m; i++) {
			int u = nextInt(), dist = nextInt();
			firstQueries[u].add(new Query(i, dist));
		}
		
		firstDfs(0);
		secondDfs(0, 0);
		
		StringBuilder res = new StringBuilder();
		
		for(int i = 0; i < m; i++) {
			if(i != 0) {
				res.append(' ');
			}
			res.append(ans[i]);
		}
		out.print(res);
	}

	public static void main(String[] args) {
		final boolean oldChecker = false;

		if (oldChecker) {
			new Thread(null, new A(), "yarrr", 1 << 24).start();
		} else {
			new A().run();
		}
	}

	public void run() {
		try {
			final String className = this.getClass().getName().toLowerCase();

			try {
				in = new BufferedReader(new FileReader(className + ".in"));
				out = new PrintWriter(new FileWriter(className + ".out"));
			} catch (FileNotFoundException e) {
				in = new BufferedReader(new InputStreamReader(System.in));
				out = new PrintWriter(System.out);
			}

			rnd = new Random();

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(42);
		}
	}

	String nextToken() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String line = in.readLine();

			if (line == null) {
				return null;
			}

			st = new StringTokenizer(line);
		}

		return st.nextToken();
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}