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;

		public Query(int id, int distance) {
			this.id = id;
			this.distance = distance;
		}
		
		
	}
	
	ArrayList<Integer>[] g;
	ArrayList<Query>[] firstQueries;
	ArrayList<Query>[] secondQueries;
	int[] ans;
	Stack<Integer> stack;
	
	static class NiceMap {
		int add;
		TreeMap<Integer, Integer> howMuch;
		
		public NiceMap(int add) {
			this.add = add;
			this.howMuch = new TreeMap<Integer, Integer>();
		}
		
		public int size() {
			return howMuch.size();
		}
		
		public int get(int needDistance) {
			needDistance -= add;
			//out.println("query: " + needDistance);
			Integer res = howMuch.get(needDistance);
			return (res == null) ? 0 : res;
		}
		
		public void add(int v) {
			//out.println("add: " + -add);
			howMuch.put(-add, 1);
		}
		
		static NiceMap merge(NiceMap a, NiceMap b) {
			if(a.size() > b.size()) {
				return merge(b, a);
			}
			
			for(int v : a.howMuch.keySet()) {
				int oldDistance = v + a.add;
				int newDistance = oldDistance - b.add;
				Integer oldValue = b.howMuch.get(newDistance);
				int oldValueInt = (oldValue == null) ? 0 : oldValue;
				oldValueInt += a.howMuch.get(v);
				b.howMuch.put(newDistance, oldValueInt);
				//out.println("MERGE: " + oldDistance + " " + newDistance);
			}
			
			return b;
		}
	}
	
	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));
				//out.println(q.id + " " + needVertex + " " + q.distance);
			}
		}
		

		stack.add(u);
		
		for(int v : g[u]) {
			firstDfs(v);
		}
		
		stack.pop();
	}
	
	NiceMap secondDfs(int u) {
		
		//out.println("Enter: " + u);
		
		NiceMap res = new NiceMap(0);
		
		for(int v : g[u]) {
			res = NiceMap.merge(res, secondDfs(v));
		}
		
		res.add += 1;
		res.add(u);
		
		/*out.println("Debug: " + u);
		
		for(int i = 0; i <= 5; i++) {
			out.print(res.get(i) + " ");
		}
		out.println("---");*/
		
		
		for(Query q : secondQueries[u]) {
			//out.println("Query: " + u + " " + q.id + " " + q.distance + " " + res.get(q.distance));
			ans[q.id] = res.get(q.distance) - 1;
		}
		
		//out.println("debug:" + u + " " + res.get(0));
		
		//out.println("exit:" + u);
		
		return res;
	}
	
	void solve() throws IOException {
		int n = nextInt();
		
		g = new ArrayList[n + 1];
		firstQueries = new ArrayList[n + 1];
		secondQueries = new ArrayList[n + 1];
		stack = new Stack<Integer>();
		
		for(int i = 0; i <= n; i++) {
			g[i] = new ArrayList<Integer>();
			firstQueries[i] = new ArrayList<Query>();
			secondQueries[i] = new ArrayList<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);
		
		for(int i = 0; i < m; i++) {
			if(i != 0) {
				out.print(' ');
			}
			out.print(ans[i]);
		}
	}

	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());
	}
}