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.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class BloodCousinsReturn {
	int[] name, level, left, right;
	ArrayList<Integer>[] T;
	int time;

	public void dfs(int i, int lev) {
		left[i] = time++;
		level[i] = lev;
		for (int j : T[i])
			dfs(j, lev + 1);
		right[i] = time - 1;
	}

	class BIT {
		int[] bit;

		public BIT(int n) {
			bit = new int[n + 1];
		}

		public int query(int i) {
			int sum = 0;
			for (i = i + 1; i > 0; i -= i & -i)
				sum += bit[i];
			return sum;
		}

		public void add(int i, int val) {
			for (i = i + 1; i < bit.length; i += i & -i)
				bit[i] += val;
		}

		public int query(int l, int r) {
			return query(r) - query(l - 1);
		}
	}

	class Event implements Comparable<Event> {
		// l = name,r = index,type = -2 in case of add
		// l = l, r = r,type = index in case of query
		public Event(int ll, int rr, int tt) {
			l = ll;
			r = rr;
			type = tt;
		}

		int l, r, type;

		public int compareTo(Event o) {
			return r - o.r;
		}
	}

	public void run() {
		InputReader in = new InputReader(System.in);
		int n = in.nextInt();
		name = new int[n + 1];
		level = new int[n + 1];
		left = new int[n + 1];
		right = new int[n + 1];
		time = 0;
		TreeMap<String, Integer> M = new TreeMap<String, Integer>();
		int cnt = 0;
		T = new ArrayList[n + 1];
		for (int i = 0; i <= n; i++)
			T[i] = new ArrayList<Integer>();
		for (int i = 1; i <= n; i++) {
			String s = in.next();
			if (!M.containsKey(s))
				M.put(s, cnt++);
			int p = in.nextInt();
			T[p].add(i);
			name[i] = M.get(s);
		}
		dfs(0, 0);
		int maxlev = 0;
		for (int i : level)
			maxlev = Math.max(maxlev, i);
		int[] count = new int[maxlev + 1];
		for (int i : level)
			count[i]++;
		int[] count2 = count.clone();
		Integer[][] levels = new Integer[maxlev + 1][];
		for (int i = 0; i < levels.length; i++)
			levels[i] = new Integer[count[i]];
		for (int i = 0; i < level.length; i++)
			levels[level[i]][--count[level[i]]] = i;
		Comparator<Integer> C = new Comparator<Integer>() {
			public int compare(Integer o1, Integer o2) {
				return left[o1] - left[o2];
			}
		};
		// for (Integer[] a : levels)
		// System.out.println(Arrays.toString(a));
		// System.out.println(Arrays.toString(left));
		// System.out.println(Arrays.toString(right));
		// System.out.println();
		for (Integer[] a : levels) {
			Arrays.sort(a, C);
			// System.out.println(Arrays.toString(a));
		}
		int q = in.nextInt();
		int[] node = new int[q];
		int[] k = new int[q];
		int[] qans = new int[q];
		for (int i = 0; i < q; i++) {
			node[i] = in.nextInt();
			k[i] = in.nextInt();
			if (level[node[i]] + k[i] <= maxlev)
				count2[level[node[i]] + k[i]]++;
		}
		// for (int i = 0; i < levels.length; i++)
		// System.out.println(Arrays.toString(levels[i]));
		// System.out.println(Arrays.toString(count2));
		Event[][] events = new Event[maxlev + 1][];
		for (int i = 0; i < events.length; i++)
			events[i] = new Event[count2[i]];
		for (int i = 0; i < q; i++) {
			int lower = left[node[i]];
			int upper = right[node[i]];
			int tlevel = level[node[i]] + k[i];
			if (tlevel > maxlev) {
				continue;
			}
			int l = 0;
			int h = levels[tlevel].length - 1;
			while (h > l) {
				int mid = (l + h) >> 1;
				if (left[levels[tlevel][mid]] >= lower)
					h = mid;
				else
					l = mid + 1;
			}
			if (left[levels[tlevel][l]] < lower) {
				events[tlevel][--count2[tlevel]] = new Event(-1, -1, -1);
				continue;
			}
			lower = l;
			l = 0;
			h = levels[tlevel].length - 1;
			while (h > l) {
				int mid = (l + h) >> 1;
				if (left[levels[tlevel][mid]] >= upper)
					h = mid;
				else
					l = mid + 1;
			}
			if (left[levels[tlevel][l]] > upper)
				l--;
			if (l < 0 || l < lower) {
				events[tlevel][--count2[tlevel]] = new Event(-1, -1, -1);
				continue;
			}
			upper = l;
			// System.out.println(i + " " + lower + " " + upper);
			events[tlevel][--count2[tlevel]] = new Event(lower, upper, i);
		}
		for (int i = 0; i < levels.length; i++)
			for (int j = 0; j < levels[i].length; j++)
				events[i][--count2[i]] = new Event(name[levels[i][j]], j, -2);
		int[] last = new int[M.size()];
		Arrays.fill(last, -1);
		BIT bit = new BIT(n);
		for (int i = 0; i < levels.length; i++) {
			Arrays.sort(events[i]);
			for (Event e : events[i]) {
				if (e.l == -1)
					continue;
				if (e.type == -2) {
					if (last[e.l] != -1)
						bit.add(last[e.l], -1);
					bit.add(e.r, 1);
					last[e.l] = e.r;
				} else {
					int r = bit.query(e.l, e.r);
					qans[e.type] = r;
				}
			}
			// clean the bit :D
			for (Event e : events[i]) {
				if (e.type != -2)
					continue;
				if (last[e.l] == e.r) {
					last[e.l] = -1;
					bit.add(e.r, -1);
				}
			}
		}
		for (int i : qans)
			System.out.println(i);
	}

	public static void main(String[] args) {
		(new BloodCousinsReturn()).run();
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}