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:
/* Codeforces Template */

import java.io.*;
import java.util.*;
import java.util.Map.Entry;

import static java.lang.Math.*;
import static java.util.Arrays.fill;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.sort;

public class Main {
	
	static long initTime;
	static final Random rnd = new Random(7777L);
	
	public static void main(String[] args) throws IOException {
		initTime = System.currentTimeMillis();
		new Thread(null, new Runnable() {
			public void run() {
				try {
					try {
						if (new File("input.txt").exists())
							System.setIn(new FileInputStream("input.txt"));
					} catch (SecurityException e) {}
//					long prevTime = System.currentTimeMillis();
					new Main().run();
//					System.err.println("Total time: " + (System.currentTimeMillis() - prevTime) + " ms");
//					System.err.println("Memory status: " + memoryStatus());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}, "1", 1L << 24).start(); 
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
		in.close();
	}
	
	/*************************************************************** 
	 * Solution
	 **************************************************************/

	int vNum;
	int root = 0;
	MultiList tree;
	QueryList query;
	
	int LOG;
	int[][] prev;
	int[] dist;
	
	int[] ans;
	
	void solve() throws IOException  {
		vNum = nextInt() + 1;
		tree = new MultiList(vNum, vNum - 1);
		
		for (int i = 1; i < vNum; i++) {
			int p = nextInt();
			tree.add(p, i);
		}
		
		precalc();
		
		int qNum = nextInt();
		ans = new int [qNum];
		query = new QueryList(vNum, qNum);
		
		for (int i = 0; i < qNum; i++) {
			int v = nextInt();
			int p = nextInt();
			int a = anc(v, p);
			if (a > root) {
				query.add(a, dist[a] + p, i);
			}
		}
		
		dfs(root, -1);
		
		printArray(ans);
	}
	
	TreeMap<Integer, Integer> dfs(int v, int p) {
		TreeMap<Integer, Integer> ret = null;
		
		for (int i = tree.head[v]; i != 0; i = tree.next[i]) {
			int nv = tree.vert[i];
			if (nv != p) {
				ret = merge(ret, dfs(nv, v));
			}
		}
		
		if (ret == null) {
			ret = new TreeMap<Integer, Integer>();
		}
		
		add(ret, dist[v], 1);
		
		for (int i = query.head[v]; i != 0; i = query.next[i]) {
			int d = query.depth[i];
			int id = query.number[i];
			ans[id] = get(ret, d) - 1;
		}
		
		return ret;
	}

	int get(TreeMap<Integer, Integer> cache, int id) {
		Integer ret = cache.get(id);
		return ret == null ? 0 : ret;
	}

	void add(TreeMap<Integer, Integer> cache, int key, int value) {
		Integer old = cache.get(key);
		if (old == null) {
			cache.put(key, value);
		} else {
			cache.put(key, old + value);
		}
	}

	TreeMap<Integer, Integer> merge(TreeMap<Integer, Integer> cache1, TreeMap<Integer, Integer> cache2) {
		if (cache1 == null) return cache2;
		if (cache2 == null) return cache1;
		
		if (cache1.size() < cache2.size()) {
			TreeMap<Integer, Integer> tref = cache1;
			cache1 = cache2;
			cache2 = tref;
		}
		
		for (Entry<Integer, Integer> e : cache2.entrySet()) {
			add(cache1, e.getKey(), e.getValue());
		}
		
		return cache1;
	}

	int anc(int v, int d) {
		if (dist[v] - d < 0) {
			return -1;
		}
		int p = v;
		for (int l = LOG; l >= 0; l--) {
			while (dist[prev[p][l]] > dist[v] - d) {
				p = prev[p][l];
			}
		}
		return prev[p][0];
	}

	void precalc() {
		for (LOG = 1; (1 << LOG) <= vNum; LOG++);
		dist = new int [vNum];
		prev = new int [vNum][LOG + 1];
		dfs1(root, -1, 0);
	}

	void dfs1(int v, int p, int d) {
		dist[v] = d;
		prev[v][0] = max(0, p);
		
		for (int l = 1; l <= LOG; l++) {
			prev[v][l] = prev[prev[v][l - 1]][l - 1];
		}
		
		for (int i = tree.head[v]; i != 0; i = tree.next[i]) {
			int nv = tree.vert[i];
			if (nv != p) {
				dfs1(nv, v, d + 1);
			}
		}
		
	}

	class MultiList {
		int[] head;
		int[] next;
		int[] vert;
		
		int cnt = 1;
		
		MultiList(int vNum, int eNum) {
			this.head = new int [vNum];
			this.next = new int [eNum + 1];
			this.vert = new int [eNum + 1];
		}
		
		void add(int u, int v) {
			next[cnt] = head[u];
			vert[cnt] = v;
			head[u] = cnt++;
		}
	}
	
	class QueryList {
		int[] head;
		int[] next;
		int[] depth;
		int[] number;
		
		int cnt = 1;
		
		QueryList(int vNum, int qNum) {
			this.head = new int [vNum];
			this.next = new int [qNum + 1];
			this.depth = new int [qNum + 1];
			this.number = new int [qNum + 1];
		}
		
		void add(int v, int d, int n) {
			next[cnt] = head[v];
			depth[cnt] = d;
			number[cnt] = n;
			head[v] = cnt++;
		}
	}
	
	/*************************************************************** 
	 * Input 
	 **************************************************************/
	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");
	
	String nextToken() throws IOException {
		while (!st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.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());
	}
	
	int[] nextIntArray(int size) throws IOException {
		int[] ret = new int [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextInt();
		return ret;
	}
	
	long[] nextLongArray(int size) throws IOException {
		long[] ret = new long [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextLong();
		return ret;
	}
	
	double[] nextDoubleArray(int size) throws IOException {
		double[] ret = new double [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextDouble();
		return ret;
	}
	
	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}
	
	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			st = new StringTokenizer(s);
		}
		return false;
	}
	
	/*************************************************************** 
	 * Output 
	 **************************************************************/
	void printRepeat(String s, int count) {
		for (int i = 0; i < count; i++)
			out.print(s);
	}
	
	void printArray(int[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(long[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array, String spec) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.printf(Locale.US, spec, array[i]);
		}
		out.println();
	}
	
	void printArray(Object[] array) {
		if (array == null || array.length == 0)
			return;
		boolean blank = false;
		for (Object x : array) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	@SuppressWarnings("rawtypes")
	void printCollection(Collection collection) {
		if (collection == null || collection.isEmpty())
			return;
		boolean blank = false;
		for (Object x : collection) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	/*************************************************************** 
	 * Utility
	 **************************************************************/
	static String memoryStatus() {
		return (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory() >> 20) + "/" + (Runtime.getRuntime().totalMemory() >> 20) + " MB";
	}
	
	static void checkMemory() {
		System.err.println(memoryStatus());
	}
	
	static long prevTimeStamp = Long.MIN_VALUE;
	
	static void updateTimer() {
		prevTimeStamp = System.currentTimeMillis();
	}
	
	static long elapsedTime() {
		return (System.currentTimeMillis() - prevTimeStamp);
	}
	
	static void checkTimer() {
		System.err.println(elapsedTime() + " ms");
	}
}