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:
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF208E extends PrintWriter {
	CF208E() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF208E o = new CF208E(); o.main(); o.flush();
	}

	int[] next, jj; int $ = 1;
	int link(int l, int j) {
		next[$] = l; jj[$] = j;
		return $++;
	}
	int[] ao, dd; int[][] pp; int ln;
	int[] ll, rr; int time;
	Integer[] ii;
	void init(int n, int m) {
		next = new int[1 + m]; jj = new int[1 + m];
		ao = new int[n];
		dd = new int[n];
		ln = 0;
		while (1 << ln + 1 < n)
			ln++;
		pp = new int[ln + 1][n];
		ll = new int[n]; rr = new int[n];
		ii = new Integer[n];
		for (int i = 0; i < n; i++)
			ii[i] = i;
	}
	void dfs(int i, int d) {
		dd[i] = d;
		ll[i] = time++;
		for (int h = 1; 1 << h <= d; h++)
			pp[h][i] = pp[h - 1][pp[h - 1][i]];
		for (int l = ao[i]; l != 0; l = next[l]) {
			int j = jj[l];
			dfs(j, d + 1);
		}
		rr[i] = time;
	}
	int find(int n, int d, int l) {
		int lower = -1, upper = n;
		while (upper - lower > 1) {
			int i = (lower + upper) / 2;
			int i_ = ii[i];
			if (dd[i_] < d || dd[i_] == d && ll[i_] < l)
				lower = i;
			else
				upper = i;
		}
		return lower;
	}
	void main() {
		int n = sc.nextInt();
		init(n, n - 1);
		for (int i = 0; i < n; i++) {
			int p = sc.nextInt() - 1;
			pp[0][i] = p;
			if (p != -1)
				ao[p] = link(ao[p], i);
		}
		for (int i = 0; i < n; i++)
			if (pp[0][i] == -1)
				dfs(i, 0);
		Arrays.sort(ii, (i, j) -> dd[i] != dd[j] ? dd[i] - dd[j] : ll[i] - ll[j]);
		int m = sc.nextInt();
		while (m-- > 0) {
			int i = sc.nextInt() - 1;
			int d = sc.nextInt();
			int d_ = dd[i], ans = 0;
			if (d_ >= d) {
				for (int h = ln; h >= 0; h--)
					if (1 << h <= d) {
						i = pp[h][i];
						d -= 1 << h;
					}
				ans = find(n, d_, rr[i]) - find(n, d_, ll[i]) - 1;
			}
			print(ans + " ");
		}
		println();
	}
}