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.FileReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Locale;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;


public class Solution implements Runnable {
	
	BufferedReader in;
	PrintWriter out;
	StringTokenizer st;
	
	String nextToken() throws Exception {
		while (st == null || !st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		return st.nextToken();
	}
	
	int nextInt() throws Exception {
		return Integer.parseInt(nextToken());
	}
	
	long nextLong() throws Exception {
		return Long.parseLong(nextToken());
	}
	
	final int maxc = 17;
	
	class Vert {
		int n, l, i;
		Vert(int q, int w, int e) {
			n = q; l = w; i = e;
		}
	}
	
	class V {
		int e;
		V next;
		V(int q, V w) {
			e = q; next = w;
		}
	}
	
	int n;
	V[] v;
	int[] ind, level;
	int[][] pr;
	boolean[] w;
	Vert[] vert;
	int[] levbeg;
	Vert[] vsort;
	int qq = 0;
	
	void dfs(int q, int pred, int lev) {
		w[q] = true;
		ind[q] = level[lev]++;
		vsort[qq++] = vert[q] = new Vert(q, lev, ind[q]);
		Arrays.fill(pr[q], -1);
		pr[q][0] = pred;
		for (int i = 1; i < maxc; i++) {
			if (pr[q][i - 1] != -1) pr[q][i] = pr[pr[q][i - 1]][i - 1];
		}
		for (V r = v[q]; r != null; r = r.next) {
			dfs(r.e, q, lev + 1);
		}
	}
	
	int count(int[][] a, int q, int p) {
		int ans = q;
		int st = 0;
		while (p > 0) {
			if (p % 2 == 1) {
				ans = a[ans][st];
				if (ans == -1) return ans;
			}
			p /= 2;
			st++;
		}
		return ans;
	}
	
	int prc(int q, int p) {
		return count(pr, q, p);
	}
	
	int bsear(int b, int e, int pred, int p, boolean eq) {
		if (eq) {
			if (prc(vsort[b].n, p) == pred) return b;
		}
		while (e > b + 1) {
			int m = (b + e) / 2;
			if (!eq ^ (prc(vsort[m].n, p) != pred)) b = m; else e = m;
		}
		return eq? e : b;
	}
	
	int ans(int q, int pred, int p) {
		if (p == 0) return 1;
		return -bsear(levbeg[vert[q].l], vert[q].i, pred, p, true) + 
				bsear(vert[q].i, levbeg[vert[q].l + 1], pred, p, false) + 1;
	}
	
	int answer(int q, int p) {
		int pred = prc(q, p);
		if (pred == -1) return 0;
		return ans(q, pred, p) - ans(q, pred, p - 1);
	}
	
	int z1 = 1, z2 = 1;
	
	void solve() throws Exception {
		n = nextInt();
		v = new V[n];
		for (int i = 0; i < n; i++) {
			int q = nextInt() - 1;
			if (q >= 0) v[q] = new V(i, v[q]);
		}
		ind = new int[n];
		level = new int[n];
		pr = new int[n][maxc];
		vert = new Vert[n];
		vsort = new Vert[n];
		levbeg = new int[n + 1];
		w = new boolean[n];
		for (int i = 0; i < n; i++) if (!w[i]) dfs(i, -1, 0);
		Arrays.sort(vsort, new Comparator<Vert>() {
			@Override
			public int compare(Vert arg0, Vert arg1) {
				if (arg0.l == arg1.l) return arg0.i - arg1.i; 
				return arg0.l - arg1.l;
			}
		});
		for (int i = 0; i < n; i++) {
			vert[vsort[i].n].i = i; 
		}
		int lb = 0;
		for (int i = 0; i < n; i++) {
			if (i == 0 || vsort[i - 1].l == lb - 1 && vsort[i].l == lb) {
				 levbeg[lb++] = i;
			}
		}
		levbeg[lb] = n;
		int m = nextInt();
		for (int i = 0; i < m; i++) {
			out.print(answer(z1 = nextInt() - 1, z2 = nextInt()) + " ");
		}
	}
	
	public void run() {
		try {
			Locale.setDefault(Locale.UK);
			in = new BufferedReader(new InputStreamReader(System.in));
			//in = new BufferedReader(new FileReader("input.txt"));
			out = new PrintWriter(System.out);
			solve();
		} catch (Exception e) {
			e.printStackTrace(out);
			out.close();
			System.exit(0);
		} finally {
			out.close();
		}
	}

	public static void main(String[] args) {
		new Thread(null, new Solution(), "1", 1 << 28).start();
	}

}