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.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class DilworthTheorem {
	static String[] names;
	static int[][] adj;
	static int sz[], lvl[];
	static int[] par;
	static boolean vis[];
	static Scanner sc = new Scanner();

	public static void main(String[] args) throws IOException {
		PrintWriter pw = new PrintWriter(System.out);

		int n = sc.nextInt();
		vis = new boolean[n];
		par = new int[n];
		lvl = new int[n];
		sz = new int[n];
		names = new String[n];
		int[] from = new int[n];
		int[] to = new int[n];
		for (int i = 0; i < n; i++) {
			names[i] = sc.next();
			from[i] = sc.nextInt() - 1;
			par[i] = from[i];
			to[i] = i;
		}

		adj = packD(n, from, to);

		for (int i = 0; i < n; i++) {
			if (sz[i] == 0) {
				size(i, -1);
			}
		}

		for (int i = 0; i < n; i++) {
			if (par[i] == -1) {
				bfs(i);
			}
		}

		int m = sc.nextInt();
		set = new TreeSet[n + 1];
		qu = new ArrayList[n];
		ans = new int[m];
		for (int i = 0; i < m; i++) {
			int v = sc.nextInt() - 1;
			int k = sc.nextInt() + lvl[v];
			if(k > n){
				ans[i] = 0 ;
				continue;
			}
			if (qu[v] == null) {
				qu[v] = new ArrayList<Query>();
			}
			qu[v].add(new Query(i, k));
		}
		for (int i = 0; i < set.length; i++) {
			set[i] = new TreeSet<>();
		}
		for (int i = 0; i < n; i++) {
			if (lvl[i] == 0)
				solve(i, -1, false);
		}

		for (int i = 0; i < m; i++) {
			pw.println(ans[i]);
		}

		pw.flush();
		pw.close();
	}

	static int ans[];
	static TreeSet<String>[] set;

	private static void solve(int u, int p, boolean keep) {
		int big = -1;
		int mx = -1;
		for (int v : adj[u]) {
			if (v != p && sz[v] > mx) {
				mx = sz[v];
				big = v;
			}
		}
		for (int v : adj[u]) {
			if (v != p && v != big) {
				solve(v, u, false);
			}
		}
		if (big != -1) {
			solve(big, u, true);
		}
		add(u, p, big);

		if (qu[u] != null) {
			for (Query query : qu[u]) {
				ans[query.idx] =  set[query.kth].size() ;
			}
		}
		if (!keep) {
			remove(u, p);
		}
	}

	private static void remove(int u, int p) {
		set[lvl[u]].remove(names[u]);
		for (int v : adj[u])
			if (v != p)
				remove(v, u);
	}

	private static void add(int u, int p, int big) {
		set[lvl[u]].add(names[u]);
		for (int v : adj[u])
			if (v != p && v != big)
				add(v, u, big);
	}

	static ArrayList<Query> qu[];

	private static void bfs(int root) {
		vis[root] = true;
		lvl[root] = 0;
		Queue<Integer> q = new LinkedList<>();
		q.add(root);
		while (!q.isEmpty()) {
			int poll = q.poll();
			for (Integer i : adj[poll]) {
				if (!vis[i]) {
					vis[i] = true;
					lvl[i] = lvl[poll] + 1;
					q.add(i);
				}
			}
		}

	}

	private static void size(int u, int p) {
		sz[u]++;
		for (int v : adj[u])
			if (v != p) {
				size(v, u);
				sz[u] += sz[v];
			}
	}

	static int[][] packD(int n, int[] from, int[] to) {
		int[][] g = new int[n][];
		int[] p = new int[n];
		for (int f : from)
			if (f != -1)
				p[f]++;
		for (int i = 0; i < n; i++)
			g[i] = new int[p[i]];
		for (int i = 0; i < from.length; i++)
			if (from[i] != -1) {
				g[from[i]][--p[from[i]]] = to[i];
			}
		return g;
	}

	static class Query {
		int idx, kth;

		public Query(int idx, int kth) {
			this.idx = idx;
			this.kth = kth;
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public Scanner(FileReader fileReader) throws FileNotFoundException {
			br = new BufferedReader(fileReader);
		}

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

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

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}
}