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

public class B {
    public static void main(String[] args)throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
            int n = sc.nextInt();
            String[] arr = new String[n];
            adjmat = new ArrayList[n];
            for(int i=0;i<adjmat.length;i++)adjmat[i]= new ArrayList<>();
            ArrayList<Integer>roots = new ArrayList<>();
            for(int i=0;i<n;i++){
                String s = sc.next();
                int p = sc.nextInt()-1;
                arr[i] = s;
                if (p>=0){
                    adjmat[i].add(p);
                    adjmat[p].add(i);
                }else{
                    roots.add(i);
                }
            }
            int m = sc.nextInt();
            Query = new ArrayList[n];
            for(int i=0;i<n;i++)Query[i]= new ArrayList<>();
            for(int i=0;i<m;i++){
                int v = sc.nextInt()-1;
                int k = sc.nextInt();
                Query[v].add(new query(k,i));
            }
            size= new int[n];
            dep = new int[n];
            S = new ArrayList[n];
            h = new HashMap<>();
            for(int root:roots) {
                sz(root,-1,0);
                dfs(root, -1, false, arr);
            }
            int[] result = new int[m];
            for(int i=0;i<n;i++){
                for(query q:Query[i]){
                    result[q.index] = q.ans;
                }
            }
            for(int i=0;i<m;i++)
                pw.println(result[i]);

        pw.flush();
        pw.close();
    }
    static class Pair implements Comparable<Pair>{
        int index;
        int dist;
        public Pair(int index,int dist){
            this.index = index;
            this.dist = dist;
        }
        public int compareTo(Pair p){
            if(this.dist==p.dist)
                return Integer.compare(this.index,p.index);
            return Integer.compare(this.dist,p.dist);
        }
        public String toString(){
            return index+" " + dist;
        }

    }
    static ArrayList<Integer>[] S,adjmat;
    static ArrayList<query>[] Query;
    static int[] size,dep;
    static int sz(int a,int p,int d){
        int res = 1;
        for(int u:adjmat[a]){
            if(u!=p)
                res+=sz(u,a,d+1);
        }
        dep[a] = d;
        return size[a] = res;
    }
    static HashMap<Integer,HashMap<String,Integer>>h;
    static void dfs(int a,int p,boolean keep,String[] arr){
        int mx = -1,big = -1;
        for(int u:adjmat[a]){
            if(u!=p && size[u]>mx){
                mx= size[u];
                big = u;
            }
        }
        for(int u:adjmat[a]){
            if(u!=p && u!=big)
                dfs(u,a,false,arr);
        }
        if(big!=-1){
            dfs(big,a,true,arr);
            S[a] = S[big];
        }else{
            S[a] = new ArrayList<>();
        }
        S[a].add(a);
        if(!h.containsKey(dep[a]))h.put(dep[a],new HashMap<>());
        HashMap<String,Integer> tmp = h.get(dep[a]);
        tmp.put(arr[a],tmp.getOrDefault(arr[a],0)+1);
        for(int u:adjmat[a]){
            if(u==p || u==big)continue;
            for(int v:S[u]){
                if(!h.containsKey(dep[v]))h.put(dep[v],new HashMap<>());
                tmp = h.get(dep[v]);
                tmp.put(arr[v],tmp.getOrDefault(arr[v],0)+1);
//                System.out.println(tmp);
                S[a].add(v);
            }
        }
        for(query q:Query[a]){
            int d = q.k + dep[a];
            q.ans = h.getOrDefault(d,new HashMap<>()).size();
        }
        if(!keep) {
            for (int u : S[a]) {
                tmp = h.get(dep[u]);
                tmp.put(arr[u],tmp.getOrDefault(arr[u],0)-1);
                if(tmp.getOrDefault(arr[u],0)==0)tmp.remove(arr[u]);
            }
        }
    }
    static class query{
        int k,ans,index;
        public query(int k,int index){
            this.k = k;
            this.index = index;
        }
    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        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 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 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 boolean ready() throws IOException {
            return br.ready();

        }
    }
}