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.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Solution implements Runnable {
	private BufferedReader br;
	private StringTokenizer tok;
	private PrintWriter out;
	
	public static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
	public static final int MAXH = 20;
	
	ArrayList<Integer>[] g;
	ArrayList<Integer>[] m;
	
	int[] p;
	int[] h;
	int[] cnt;
	int[] id;
	int[][] dp;
	
	int currentNumber;
	
	@SuppressWarnings("unchecked")
	void init(int n) {
		g = new ArrayList[n];
		for (int i = 0; i < n; ++i) {
			g[i] = new ArrayList<Integer>();
		}
		m = new ArrayList[n];
		for (int i = 0; i < n; ++i) {
			m[i] = new ArrayList<Integer>();
		}
		p = new int[n];
		h = new int[n];
		cnt = new int[n];
		id = new int[n];
		dp = new int[n][MAXH];
	}
	
	void dfs(int v, int height) {
		h[v] = height;
		cnt[v] = 1;
		id[v] = currentNumber++;
		m[h[v]].add(id[v]);
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v].get(i);
			dfs(to, height + 1);
			cnt[v] += cnt[to];
		}
	}
	
	void prepare(int n) {
		for (int j = 0; j < MAXH; ++j)
			for (int i = 0; i < n; ++i)
				if (j == 0) {
					dp[i][j] = p[i];
				} else {
					dp[i][j] = dp[dp[i][j - 1]][j - 1];
				}
	}
	
	int getAncestor(int v, int d) {
		int tmp = d;
		int u = v;
		for (int i = MAXH - 1; i >= 0; --i)
			if (tmp >= (1 << i)) {
				tmp -= 1 << i;
				u = dp[u][i];
			}
		if (h[v] - h[u] < d)
			return - 1;
		return u;
	}
	
	int query(int v, int height) {
		int tmp = id[v] + 1;
		int l = 0,
			r = m[height].size() - 1;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (tmp > m[height].get(mid)) {
				l = mid + 1;
			} else {
				r = mid;
			}
		}
		while (m[height].get(l) < tmp) {
			++l;
		}
		int cur = l;
		tmp = id[v] + cnt[v];
		l = 0;
		r = m[height].size() - 1;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (tmp > m[height].get(mid)) {
				l = mid + 1;
			} else {
				r = mid;
			}
		}
		while (m[height].get(l) > tmp) {
			--l;
		}
		return l - cur;
	}
		
	void solve() throws IOException {
		int n = nextInt();
		init(n);
		ArrayList<Integer> roots = new ArrayList<Integer>();
		for (int i = 0; i < n; ++i) {
			int pv = nextInt();
			if (pv == 0) {
				roots.add(i);
				p[i] = i;
			} else {
				g[pv - 1].add(i);
				p[i] = pv - 1;
			}
		}
		for (int i = 0; i < roots.size(); ++i) {
			dfs(roots.get(i), 0);
		}
		prepare(n);
		int q = nextInt();
		for (int i = 0; i < q; ++i) {
			int u = nextInt() - 1;
			int d = nextInt();
			int v = getAncestor(u, d);
			if (v == -1) {
				out.print("0 ");
			} else {
				out.print(query(v, h[u]) + " ");
			}
		}
	}
		
	public void run() {
		try {
			if (ONLINE_JUDGE) {
				br = new BufferedReader(new InputStreamReader(System.in));
				out = new PrintWriter(System.out);
			} else {
				br = new BufferedReader(new FileReader(new File("input.txt")));
				out = new PrintWriter(new File("output.txt"));
			}
			solve();
			br.close();
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(1);
		}
	}
	
	public static void main(String[] args) {
		new Solution().run();
	}	
	
	String nextToken() throws IOException {
		while (tok == null || !tok.hasMoreTokens())
			tok = new StringTokenizer(br.readLine());
		return tok.nextToken();
	}
	
	String nextString() throws IOException {
		return 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());
	}
	
	BigInteger nextBigInteger() throws IOException {
		return new BigInteger(nextToken());
	}
}