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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeSet;

/**
 * Created by pranavps
 */

/**
 *
 * N = 1e5 -> N*sqrt(N) will work but not for N = 1e6
 */
public class LCAProblem {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        int testcases = 1;//TODO: change to in.nextInt() if required
        for (int testcase = 1; testcase <= testcases ; testcase++) {
            solver.solve(testcase, in, out);
        }
        out.close();
    }

    static class Task {
        private int id = 0;
        private HashMap<Integer,Integer> hm;
        private boolean[] visited;
        private ArrayList<ArrayList<Integer>> adjList;
        private int[] cnt;
        private HashMap<Integer, ArrayList<Integer>> heights;
        private HashMap<Integer,Integer> hmHeight;
        private static long MOD = (long)(1e9+7);

        public void solve(int testcase, InputReader in, PrintWriter out) {
            int N = in.nextInt();
            int[] parent = in.nextIntArray(N);
            ArrayList<Integer> roots = new ArrayList<>();
            adjList = new ArrayList<>();
            for (int i = 0; i <= N; i++) {
                adjList.add(new ArrayList<>());
            }
            for (int i = 0; i < N; i++) {
                if(parent[i] == 0)
                    roots.add(i+1);
                else{
                    adjList.get(parent[i]).add(i+1);
                }
            }
            hm = new HashMap<>();
            hmHeight = new HashMap<>();
            visited = new boolean[N+1];
            cnt = new int[N];
            heights = new HashMap<>();
            for (int i = 0; i < roots.size(); i++) {
                dfs(roots.get(i),0);
            }

            int[] arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[hm.get(i+1)] = (parent[i]>0)?hm.get(parent[i]):-1;
            }
            LCA lca = new LCA(arr);
            lca.build();
            int m = in.nextInt();
            BinarySearch bs = new BinarySearch();
            for (int i = 0; i < m; i++) {
                int v = hm.get(in.nextInt());
                int p = in.nextInt();
                int anc;
                if(p > hmHeight.get(v))
                    anc = -1;
                else
                    anc = lca.pthAncestorQuery(v,p);
                if(anc == -1){
                    out.print((i==0)?0:(" "+0));
                    continue;
                }
                ArrayList<Integer> al = heights.get(hmHeight.get(v));
                int answer = bs.binarySearch(al, anc+cnt[anc], 0, al.size())-bs.binarySearch(al, anc,0, al.size());
                answer--;
                out.print((i==0)?answer:(" "+answer));
            }
            out.println();
        }

        private void dfs(int x, int h){
            if(!heights.containsKey(h))
                heights.put(h,new ArrayList<>());
            heights.get(h).add(id);
            hmHeight.put(id,h);
            hm.put(x,id);
            id++;
            visited[x] = true;
            cnt[hm.get(x)] = 1;
            for (int i = 0; i < adjList.get(x).size(); i++) {
                int child = adjList.get(x).get(i);
                if(!visited[child])
                    dfs(child,h+1);
                cnt[hm.get(x)] += cnt[hm.get(child)];
            }
        }
    }

    /**
     * Algorithm
     * Binary Search Algorithm
     * @author pranavps
     * @version 1.0
     * @since 23/12/17
     */
    static class BinarySearch {

        public BinarySearch(){

        }

        /**
         * binary search algorithm to return leftmost index of a value in an array in range [lo,hi)
         * if the value does not exist then it returns the index of first larger element in the array
         * encoded as -(insertion point)-1
         * @param arr
         * @param key
         * @param lo
         * @param hi
         * @return leftmost index of key in arr if present otherwise leftmost index of a number strictly greater than key
         *          in format -(index)-1
         */
        public int binarySearch(int[] arr, int key, int lo, int hi){// [lo,hi)
            int mid = -1;
            boolean found = false;
            while(lo < hi){
                mid = lo + (hi-lo)/2;
                if(arr[mid] == key){
                    found = true;
                    hi = mid;
                }
                else if(arr[mid] < key){
                    lo = mid+1;
                }
                else{
                    hi = mid;
                }
            }

            return found?(lo):(-lo-1);
        }

        public int binarySearch(ArrayList<Integer> arr, int key, int lo, int hi){// [lo,hi)
            int mid;
            while(lo < hi){
                mid = lo + (hi-lo)/2;
                if(arr.get(mid) == key){
                    hi = mid;
                }
                else if(arr.get(mid) < key){
                    lo = mid+1;
                }
                else{
                    hi = mid;
                }
            }
            return lo;
        }
    }


    /**
     * Data Structure
     * Sparse Table data structure
     * Substitute for segment tree in case of immutable data
     * @author pranavps
     * @version 1.0
     * @since 19/12/17
     */
    static class LCA {
        int[] arr;//array of immediate parents, -1 if no parent
        int N;
        int logN;
        int[][] table;

        /**
         * Creates the sparse table for LCA problem
         * Nodes are numbered 0 to N-1 where N is length of array
         * @param arr array of immediate parents, -1 if no parent
         */
        public LCA(int[] arr){
            this.arr = arr;
            N = arr.length;
            logN = log(N);
            table = new int[N][logN+1];
            for (int j = 0; j <= logN; j++) {
                for (int i = 0; i < N; i++) {
                    table[i][j] = (j==0)?arr[i]:-1;
                }
            }
        }

        /**
         *
         * @param N number >= 1
         * @return floor of log base 2 of N
         */
        private int log(long N){
            int ans = 0;
            long temp = 1;
            while(temp <= N){
                ans++;
                temp <<= 1;
            }
            ans--;
            return ans;
        }

        /**
         * This will build the sparse table from given array
         */
        public void build(){

            for(int j = 1; j <= logN; j++)
                for(int i = 0; i < N; i++)
                    if(table[i][j-1] != -1)
                        table[i][j] = table[table[i][j-1]][j-1];
        }

        /**
         *
         * @param v node in the tree
         * @param p ancestor number
         * @return pth ancestor of v if exists, else -1
         */
        public int pthAncestorQuery(int v, int p){
            for (int i = logN; i >= 0; i--) {
                if(v == -1)
                    break;
                if((p&(1<<i))!=0)
                    v = table[v][i];
            }
            return v;
        }
    }


    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public int[] nextIntArray(int n){
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

        public long[] nextLongArray(int n){
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }
    }
}