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 CF208E 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 CF208E(), "", 256 * 1024 * 1024).start();
	}
	
//------------------------------------------------------------------------------

	class Query {
		int h, i;

		public Query(int h, int i) {
			this.h = h;
			this.i = i;
		}
	}
	
	class NormalDeque<T> {
		
		private Object[] array;
		private int size, head, tail, capacity;
		
		public NormalDeque() {
			capacity = 16;
			array = new Object[capacity];
			size = head = tail = 0;
		}
		
		public boolean isEmpty() {
			return head == tail;
		}
		
		public int size() {
			return size;
		}
		
		private int next(int i) {
			if (i == capacity - 1) {
				return 0;
			}
			return i + 1;
		}
		
		private int previous(int i) {
			if (i == 0) {
				return capacity - 1;
			}
			return i - 1;
		}
		
		private void resize() {
			Object[] newArray = new Object[capacity << 1];
			for (int i = head, j = 0; j < size; i = next(i), j++) {
				newArray[j] = array[i];
			}
			head = 0;
			tail = size;
			capacity <<= 1;
			array = newArray;
		}
		
		public void addLast(T x) {
			if (isEmpty()) {
				resize();
			}
			array[tail] = x;
			tail = next(tail);
			size++;
		}
		
		public void addFirst(T x) {
			if (isEmpty()) {
				resize();
			}
			head = previous(head);
			array[head] = x;
			size++;
		}
		
		public T get(int i) {
			if (head + i < capacity) {
				return (T) array[head + i];
			}
			return (T) array[head + i - capacity];
		}
		
		public void set(int i, T x) {
			if (head + i < capacity) {
				array[head + i] = x;
				return;
			}
			array[head + i - capacity] = x;
		}

		@Override
		public String toString() {
			Object[] t = new Object[size];
			for (int i = head, j = 0; j < size; i = next(i), j++) {
				t[j] = array[i];
			}
			return Arrays.deepToString(t);
		}

	}
	
	int n, m;
	List<Integer>[] graph;
	int[] height;
	int[][] parent;
	List<Query>[] queries;
	NormalDeque<Integer>[] dp;
	int[] ans;
	
	void solve() throws IOException {
		n = readInt();
		graph = new List[n];
		for (int i = 0; i < n; i++) {
			graph[i] = new ArrayList<Integer>();
		}
		parent = new int[18][n];
		for (int i = 0; i < n; i++) {
			int p = readInt() - 1;
			if (p != -1) {
				graph[p].add(i);
			} else {
				p = i;
			}
			parent[0][i] = p;
		}
		height = new int[n];
		for (int i = 0; i < n; i++) {
			if (parent[0][i] == i) {
				dfs0(i, 0);
			}
		}
		for (int lvl = 1; lvl < 18; lvl++) {
			for (int i = 0; i < n; i++) {
				parent[lvl][i] = parent[lvl-1][parent[lvl-1][i]];
			}
		}
		m = readInt();
		queries = new List[n];
		for (int i = 0; i < n; i++) {
			queries[i] = new ArrayList<Query>();
		}
		for (int i = 0; i < m; i++) {
			int x = readInt() - 1;
			int h = readInt();
			int p = getParent(x, h);
			if (p != -1) {
				queries[p].add(new Query(h, i));
			}
		}
		dp = new NormalDeque[n];
		ans = new int[m];
		for (int i = 0; i < n; i++) {
			if (parent[0][i] == i) {
				dfs(i);
			}
		}
		for (int i = 0; i < m; i++) {
			if (ans[i] > 0) {
				ans[i]--;
			}
			out.print(ans[i]);
			if (i != m-1) out.print(' '); else out.println();
		}
	}

	private void dfs(int x) {
		for (int y : graph[x]) {
			dfs(y);
		}
		for (int y : graph[x]) {
			if (dp[x] == null || dp[x].size() < dp[y].size()) {
				dp[x] = dp[y];
			}
		}
		if (dp[x] == null) {
			dp[x] = new NormalDeque<Integer>();
		}
		dp[x].addFirst(1);
		for (int y : graph[x]) {
			if (dp[x] != dp[y]) {
				for (int k = 0; k < dp[y].size(); k++) {
					dp[x].set(k + 1, dp[x].get(k + 1) + dp[y].get(k));
				}
			}
		}
		for (Query q : queries[x]) {
			if (q.h < dp[x].size()) {
				ans[q.i] = dp[x].get(q.h);
			}
		}
	}

	private int getParent(int x, int h) {
		if (height[x] < h) {
			return -1;
		}
		for (int lvl = 17; lvl >= 0; lvl--) {
			if (h >= (1 << lvl)) {
				h -= (1 << lvl);
				x = parent[lvl][x];
			}
		}
		return x;
	}
	
	private void dfs0(int x, int h) {
		height[x] = h;
		for (int y : graph[x]) {
			dfs0(y, h + 1);
		}
	}

}