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

public class CF246E implements Runnable {
	
	final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
	
	BufferedReader in;
	PrintWriter out;
	StringTokenizer tok;
	
	@Override
	public void run() {
		try {
			long startTime = System.currentTimeMillis();
			Locale.setDefault(Locale.US);
			if (ONLINE_JUDGE) {
				in = new BufferedReader(new InputStreamReader(System.in));
				out = new PrintWriter(System.out);
			} else {
				in = new BufferedReader(new FileReader("input.txt"));
				out = new PrintWriter("output.txt");
			}
			tok = new StringTokenizer("");
			solve();
			in.close();
			out.close();
			long endTime = System.currentTimeMillis();
			long totalMemory = Runtime.getRuntime().totalMemory();
			long freeMemory = Runtime.getRuntime().freeMemory();
			System.err.println("Time = " + (endTime - startTime) + " ms");
			System.err.println("Memory = " + ((totalMemory - freeMemory) / 1024) + " KB");
		} catch (Throwable e) {
			e.printStackTrace(System.err);
			System.exit(-1);
		}
	}
	
	String readString() throws IOException {
		while (!tok.hasMoreTokens()) {
			String line = in.readLine();
			if (line == null) return null;
			tok = new StringTokenizer(line);
		}
		return tok.nextToken();
	}
	
	int readInt() throws IOException {
		return Integer.parseInt(readString());
	}
	
	long readLong() throws IOException {
		return Long.parseLong(readString());
	}
	
	double readDouble() throws IOException {
		return Double.parseDouble(readString());
	}
	
	void debug(Object... o) {
		if (!ONLINE_JUDGE) {
			System.err.println(Arrays.deepToString(o));
		}
	}
	
	public static void main(String[] args) {
		new Thread(null, new CF246E(), "", 128 * 1024 * 1024).start();
	}
	
//------------------------------------------------------------------------------
	
	class Query {
		int id, h, ans = 0;

		public Query(int id, int h) {
			this.id = id;
			this.h = h;
		}
	}
	
	int n, m;
	List<Integer>[] a;
	int[] id;
	Map<String, Integer> ids = new HashMap<String, Integer>();
	boolean[] root;
	List<Set<Integer>>[] dp;
	List<Query>[] q;
	Query[] all;
	
	int getID(String s) {
		if (ids.containsKey(s)) {
			return ids.get(s);
		}
		int x = ids.size() + 1;
		ids.put(s, x);
		return x;
	}
	
	void mergeLists(List<Set<Integer>> cur, List<Set<Integer>> other) {
		for (int i = cur.size() - 1, j = other.size() - 1; i >= 0 && j >= 0; i--, j--) {
			Set<Integer> curSet = cur.get(i);
			Set<Integer> otherSet = other.get(j);
			if (curSet.size() < otherSet.size()) {
				cur.set(i, otherSet);
				other.set(j, curSet);
				curSet = cur.get(i);
				otherSet = other.get(j);
			}
			curSet.addAll(otherSet);
		}
	}
	
	void dfs(int x, int p) {
		for (int y : a[x]) {
			if (y == p) {
				continue;
			}
			dfs(y, x);
			if (dp[x].size() < dp[y].size()) {
				List<Set<Integer>> t = dp[x];
				dp[x] = dp[y];
				dp[y] = t;
			}
			mergeLists(dp[x], dp[y]);
		}
		Set<Integer> set = new HashSet<Integer>();
		set.add(id[x]);
		dp[x].add(set);
		for (Query query : q[x]) {
			if (query.h < dp[x].size()) {
				query.ans = dp[x].get(dp[x].size() - query.h - 1).size();
			}
		}
	}
	
	void solve() throws IOException {
		n = readInt();
		a = new List[n];
		dp = new List[n];
		root = new boolean[n];
		id = new int[n];
		q = new List[n];
		for (int i = 0; i < n; i++) {
			a[i] = new ArrayList<Integer>();
			dp[i] = new ArrayList<Set<Integer>>();
			q[i] = new ArrayList<Query>();
		}
		for (int i = 0; i < n; i++) {
			String s = readString();
			id[i] = getID(s);
			int p = readInt();
			if (p == 0) {
				root[i] = true;
			} else {
				p--;
				a[p].add(i);
			}
		}
		m = readInt();
		all = new Query[m];
		for (int i = 0; i < m; i++) {
			int x = readInt();
			int h = readInt();
			x--;
			all[i] = new Query(i, h);
			q[x].add(all[i]);
		}
		for (int i = 0; i < n; i++) {
			if (root[i]) {
				dfs(i, -1);
			}
		}
		Arrays.sort(all, new Comparator<Query>() {
			@Override
			public int compare(Query o1, Query o2) {
				return o1.id - o2.id;
			}
		});
		for (Query q : all) {
			out.println(q.ans);
		}
	}

}