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

public class BloodCousins {
    static ArrayList<Integer>[] graph;
    static int[][] bl;
//    static int[] sz;
    static int blSz;
    static int[] depth;
    static int[] ans;
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int N = scanner.nextInt();
        graph = new ArrayList[N];
        for (int i = 0; i < N; i++) graph[i] = new ArrayList<>();
        blSz = Integer.numberOfTrailingZeros(Integer.highestOneBit(N));
        bl = new int[N][blSz + 1];
        for (int[] dd : bl) Arrays.fill(dd, -1);
        int rt = -1;
        for (int i = 0; i < N; i++) {
            int r = scanner.nextInt()-1;
            if (r >= 0) {
                graph[r].add(i);
                bl[i][0] = r;
            }
        }
        for (int i = 1; i <= blSz; i++)
            for (int j = 0; j < N; j++) if (bl[j][i - 1] != -1) bl[j][i] = bl[bl[j][i - 1]][i - 1];
        //necessary to split queries here in order to avoid an N^2 runtime
        ArrayList<Pair> queries[] = new ArrayList[N];
        for (int i = 0; i < N; i++) queries[i] = new ArrayList<>();
//        sz = new int[N];
        int M = scanner.nextInt();
        ans = new int[M];
        Arrays.fill(ans, 1);
        for (int i = 0; i < M; i++) {
            int v = scanner.nextInt() - 1;
            int p = scanner.nextInt();
            for (int j = blSz; j >= 0 && v!=-1; j--) {
                if ((p & (1 << j)) > 0) v = bl[v][j];
            }
            if (v >= 0) queries[v].add(new Pair(i, p));
            else ans[i] = 0;
        }
        depth = new int[N];
        int[] d = new int[N];
        for(int i = 0; i < N; i++) {
            if (bl[i][0] == -1) dfs(i, d, queries);
        }
        for (int i = 0; i < M; i++) {
            if (i > 0) out.print(" ");
            out.print(ans[i]);
        }
        out.flush();
    }
    //Answering queries on dfs since know depth and by subtree you also know root
    public static void dfs(int cur, int[] d, ArrayList<Pair>[] q) {
        //preprocessing so we dont double dip disjoint subtrees
        if (q[cur].size() > 0) {
            for(Pair query: q[cur]) {
                ans[query.v] += d[query.d + depth[cur]];
            }
        }
        for(int edge: graph[cur]) {
            d[depth[cur]+1]++;
            depth[edge] = depth[cur] + 1;
            dfs(edge, d, q);
        }
        if (q[cur].size() > 0) {
            for(Pair query: q[cur]) {
                ans[query.v] = d[query.d + depth[cur]] - ans[query.v];
            }
        }
    }
    
    public static class Pair {
        int v, d;
        public Pair(int vv, int dd) {
            v = vv; d = dd;
        }
    }
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
    }
}