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:
//package codeforces;

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.StringTokenizer;
import java.util.TreeMap;

public class BloodCousinsReturn
{
	static String[] names;
	static int[][] adj;
	static int sz[], lvl[], vis[] , vid = 1;
	static int[] par;
	public static void main(String[] args) throws IOException
	{
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
		int n = sc.nextInt();
		par = new int[n];
		vis = new int[n]; lvl = new int[n]; sz = new int[n];
		q = 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 TreeMap[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 < 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 TreeMap<String, Integer>[] 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] != null?set[query.kth].size():0;
		
		if(!keep)
			remove(u,p);
	}
	
	private static void remove(int u, int p)
	{
		removeMap(lvl[u], names[u]);
		for (int v : adj[u])
			if(v != p)
				remove(v, u);
	}

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

	static void addMap(int idx, String s)
	{
		if(set[idx] == null)
			set[idx] = new TreeMap<String, Integer>();
		set[idx].put(s, set[idx].getOrDefault(s, 0)+1);
	}
	
	static void removeMap(int idx, String s)
	{
		Integer nw = set[idx].remove(s);
		if(nw == null)
			return;
		if(nw-1 > 0)
			set[idx].put(s, nw-1);
		
	}
	
	static ArrayList<Query> qu[];
	static int q[], s, e;
	private static void bfs(int root)
	{
		q[e++] = root;
		vis[root] = vid;
		lvl[root] = 0;
		while(s < e)
		{
			int u = q[s++];
			for (int v : adj[u])
			{
				if(vis[v] != vid)
				{
					lvl[v] = lvl[u]+1;
					vis[v] = vid;
					q[e++] = v;
				}
			}
		}
		
	}
	
	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(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}
		public Scanner(String s) throws FileNotFoundException{	br = new BufferedReader(new FileReader(new File(s)));}
		public String next() throws IOException {while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());return st.nextToken();}
		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();}
	}	
}