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.math.*;
import java.util.*;

public class CODEFORCES
{
	private InputStream is;
	private PrintWriter out;

	int n;
	ArrayList<Integer> a[], level[];
	int depth[], st[], et[], rev[];
	int len = -1;
	String b[];

	void dfs(int u, int p)
	{
		st[u] = ++len;
		rev[len] = u;
		level[depth[u]].add(st[u]);
		for (int i : a[u])
		{
			if (i == p)
				continue;
			depth[i] = depth[u] + 1;
			dfs(i, u);
		}
		et[u] = len;
	}

	int up(int l, int v)
	{
		if (l >= level.length)
			return Integer.MAX_VALUE;
		int x = 0, r = level[l].size() - 1;
		int ind = Integer.MAX_VALUE;
		while (x <= r)
		{
			int mid = x + r >> 1;
			if (level[l].get(mid) < v)
				x = mid + 1;
			else
			{
				ind = mid;
				r = mid - 1;
			}
		}
		return ind;
	}

	int down(int l, int v)
	{
		if (l >= level.length)
			return -1;
		int x = 0, r = level[l].size() - 1;
		int ind = -1;
		while (x <= r)
		{
			int mid = x + r >> 1;
			if (level[l].get(mid) > v)
				r = mid - 1;
			else
			{
				ind = mid;
				x = mid + 1;
			}
		}
		return ind;
	}

	class q implements Comparable<q>
	{
		int ind, l, r, ans, v;

		q(int d, int a, int b, int c)
		{
			v = d;
			l = a;
			r = b;
			ind = c;
		}

		public int compareTo(q o)
		{
			return Integer.compare(r, o.r);
		}
	}

	ArrayList<q> o[];
	int arr[], m;

	void update(int x)
	{
		x++;
		while (x <= m)
		{
			arr[x]++;
			x += (x & -x);
		}
	}

	int ans(int x)
	{
		int an = 0;
		x++;
		while (x > 0)
		{
			an += arr[x];
			x -= (x & -x);
		}
		return an;
	}

	void lev(int l)
	{
		long val[] = new long[level[l].size()];
		HashMap<String, Integer> map = new HashMap<String, Integer>();
		for (int i = val.length - 1; i >= 0; i--)
		{
			if (map.containsKey(b[rev[level[l].get(i)]]))
				val[i] = (((long) map.get(b[rev[level[l].get(i)]])) << 32) | ((long) i);
			else
				val[i] = (((long) val.length) << 32) | ((long) i);
			map.put(b[rev[level[l].get(i)]], i);
		}
		Collections.sort(o[l]);
		Arrays.sort(val);
		arr = new int[val.length + 1];
		m = arr.length - 1;
		int cnt = val.length - 1;
		for (int i = o[l].size() - 1; i >= 0; i--)
		{
			// out.println(l + " lll " + o[l].get(i).ind);
			if (o[l].get(i).l > o[l].get(i).r)
				continue;
			while (cnt >= 0 && (val[cnt] >> 32) > o[l].get(i).r)
				update((int) val[cnt--]);
			o[l].get(i).ans = ans(o[l].get(i).r) - ans(o[l].get(i).l - 1);
		}
		// out.println(level[l].size() + " level " + cnt + " " + o[l].size());
	}

	@SuppressWarnings("unchecked")
	void solve()
	{
		n = ni();
		a = new ArrayList[n + 1];
		level = new ArrayList[n + 1];
		depth = new int[n + 1];
		st = new int[n + 1];
		et = new int[n + 1];
		rev = new int[n + 1];
		b = new String[n + 1];
		for (int i = 0; i <= n; i++)
		{
			a[i] = new ArrayList<Integer>();
			level[i] = new ArrayList<Integer>();
		}
		b[0] = "0";
		for (int i = 1; i <= n; i++)
		{
			b[i] = ns();
			int r = ni();
			a[r].add(i);
			a[i].add(r);
		}
		dfs(0, 0);
		int m = ni();
		q c[] = new q[m];
		o = new ArrayList[n + 1];
		for (int i = 0; i <= n; i++)
			o[i] = new ArrayList<q>();
		for (int i = 0; i < m; i++)
		{
			int v = ni(), k = ni();
			c[i] = new q(v, up(depth[v] + k, st[v]), down(depth[v] + k, et[v]), i);
			// out.println(depth[v] + k + " " + c[i].l + " " + c[i].r);
			if (depth[v] + k <= n)
				o[depth[v] + k].add(c[i]);
		}
		for (int i = 1; i <= n; i++)
			lev(i);
		for (int i = 0; i < m; i++)
			out.println(c[i].ans);
	}

	void soln()
	{
		is = System.in;
		out = new PrintWriter(System.out);
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis() - s + "ms");
	}

	public static void main(String[] args)
	{
		new CODEFORCES().soln();
	}

	// To Get Input
	// Some Buffer Methods
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;

	private int readByte()
	{
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf)
		{
			ptrbuf = 0;
			try
			{
				lenbuf = is.read(inbuf);
			} catch (IOException e)
			{
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private boolean isSpaceChar(int c)
	{
		return !(c >= 33 && c <= 126);
	}

	private int skip()
	{
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	private double nd()
	{
		return Double.parseDouble(ns());
	}

	private char nc()
	{
		return (char) skip();
	}

	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b)))
		{ // when nextLine, (isSpaceChar(b) && b != '
			// ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b)))
		{
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}

	private int[] na(int n)
	{
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-')
		{
			minus = true;
			b = readByte();
		}

		while (true)
		{
			if (b >= '0' && b <= '9')
			{
				num = num * 10 + (b - '0');
			} else
			{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-')
		{
			minus = true;
			b = readByte();
		}

		while (true)
		{
			if (b >= '0' && b <= '9')
			{
				num = num * 10 + (b - '0');
			} else
			{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

	private void tr(Object... o)
	{
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
}