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 train1;


import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

import java.util.*;


public class main208E {
    public static PrintWriter out = new PrintWriter(System.out);
    public static FastScanner enter = new FastScanner(System.in);

    public static void main(String[] args) throws IOException {
        int n = enter.nextInt();
        Graph g = new Graph(n);
        for (int i = 1; i < n + 1; i++) {
            int p = enter.nextInt();
            if (p == 0) g.parents.addLast(i);
            else {
                g.add(i, p);
                g.add(p, i);
            }
        }
        g.read();

    }


    static class Graph {
        int n;
        LinkedList<Integer>[] vert;
        long[] euler;
        int[] firstTime;
        int[] height;
        long[] eulerHeight;
        LinkedList<Integer> parents = new LinkedList<>();
        LinkedList<Integer>[] queries;
        HashMap<pair, Integer> whoIsParent=new HashMap<>();
        HashMap<pair, Integer> ansMap=new HashMap<>();
        boolean used[];
        boolean was[];
        int kolVo[];

        static class pair {
            int u, w;

            public pair(int u, int w) {
                this.u = u;
                this.w = w;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                pair pair = (pair) o;
                return u == pair.u &&
                        w == pair.w;
            }

            @Override
            public int hashCode() {
                return u*(int)1e5+w;
            }
        }
        public void add(int a, int b) {
            vert[a].addLast(b);
        }


        public Graph(int n) {
            queries = new LinkedList[n + 1];
            was= new boolean[n + 1];
            kolVo= new int[n + 1];
            euler= new long[n + 1];
            firstTime= new int[n + 1];
            height= new int[n + 1];
            eulerHeight= new long[n + 1];
            this.n = n;
            vert = new LinkedList[n + 1]; //1 ,...., n
            for (int i = 1; i < n + 1; i++) {
                vert[i] = new LinkedList<>();
                queries[i] = new LinkedList<>();

            }
            used = new boolean[n + 1];
        }

        public void read() throws IOException {
            int k = enter.nextInt();
            int[] a = new int[k];
            int[] b = new int[k];
            for (int i = 0; i < k; i++) {
                a[i] = enter.nextInt();
                b[i] = enter.nextInt();
                queries[a[i]].addLast(b[i]);
            }
            for (int p : parents) {
                solve(p);
            }
            for (int i = 0; i <k ; i++) {
                out.println(ansMap.get(new pair(a[i], b[i])));
            }
            out.close();

        }
        ArrayList<Integer> order=new ArrayList<>();
        int last_euler;
        public void solve(int v) {
            last_euler=0;
            order.clear();
            DFSForMap(v);
            for (int i = 0; i <last_euler ; i++) {
                eulerHeight[i]=height[(int)euler[i]];
            }
            SegmentTree.moreThanK((int)1e6, eulerHeight, last_euler);
            for (pair p:whoIsParent.keySet()) {
                int who=whoIsParent.get(p);
                if(who==0) ansMap.put(p, 0);
                else {
                    int l=firstTime[who];
                    int r=l+kolVo[who]-1;
                    int ans=SegmentTree.queryMoreThenK(1,0, last_euler-1, l, r, height[who]+p.w)-SegmentTree.queryMoreThenK(1,0, last_euler-1, l, r, height[who]+p.w+1)-1;
                    ansMap.put(p, ans);
                }
            }
            whoIsParent.clear();

        }
        void addAnswers(int v){
            for (int s:queries[v]) {
                if(order.size()<=s) whoIsParent.put(new pair(v, s), 0);
                else whoIsParent.put(new pair(v,s), order.get(order.size()-1-s));
            }
        }

        void DFSUtilForMap(int v, boolean was[]) {
            was[v] = true;
            order.add(v);
            addAnswers(v);
            euler[last_euler]=v;
            firstTime[v]=last_euler;
            last_euler++;
            int summ=0;
            for (int n : vert[v]) {
                if (!was[n]) {
                    height[n]=height[v]+1;
                    DFSUtilForMap(n, was);
                    summ+=kolVo[n];

                }
            }
            kolVo[v]+=summ+1;
            order.remove(order.size()-1);
        }

        void DFSForMap(int v) {
            height[v]=1;
            DFSUtilForMap(v, was);
        }


    }


    static class SegmentTree {
        private static ArrayList<Long>[] treeMoreThenK;

        public static void moreThanK(long maxValue, long[] arr, int nElemnts) {
            treeMoreThenK = new ArrayList[4 * nElemnts];
            for (int i = 0; i < treeMoreThenK.length; i++)
                treeMoreThenK[i] = new ArrayList<>();
            buildMoreThenK(arr, 1, 0, nElemnts - 1, maxValue);
        }

        private static void buildMoreThenK(long[] arr, int v, int tl, int tr, long maxValue) {
            if (tl == tr) {
                treeMoreThenK[v].add(arr[tl]);
                treeMoreThenK[v].add(maxValue);
                return;
            }
            int tmp = (tl + tr) / 2;
            buildMoreThenK(arr, 2 * v, tl, tmp, maxValue);
            buildMoreThenK(arr, 2 * v + 1, tmp + 1, tr, maxValue);
            mergeMoreThanK(v, maxValue);
        }

        public static int queryMoreThenK(int v, int tl, int tr, int l, int r, long k) {// >=k
            if (l > r) return 0;
            if (tl == l && tr == r) return binSearchMoreThenK(v, k);
            int tmp = (tl + tr) / 2;
            return queryMoreThenK(2 * v, tl, tmp, l, Math.min(r, tmp), k) + queryMoreThenK(2 * v + 1, tmp + 1, tr, Math.max(tmp + 1, l), r, k);
        }

        private static int binSearchMoreThenK(int v, long k) { //find in treeMoreThenK[v] lowest el that >=k
            int l = 0;
            int r = treeMoreThenK[v].size() - 1;
            while (r - l > 1) {
                int m = (l + r) / 2;
                if (treeMoreThenK[v].get(m) < k) l = m + 1;
                else r = m;
            }
            if (treeMoreThenK[v].get(l) < k) l = r;
            return treeMoreThenK[v].size() - l - 1;
        }

        private static void mergeMoreThanK(int v, long maxValue) {
            int first1 = 0, first2 = 0;
            while (first1 < treeMoreThenK[2 * v].size() - 1 || first2 < treeMoreThenK[2 * v + 1].size() - 1) {
                if (treeMoreThenK[2 * v].get(first1) < treeMoreThenK[2 * v + 1].get(first2)) {
                    treeMoreThenK[v].add(treeMoreThenK[2 * v].get(first1));
                    first1++;
                } else {
                    treeMoreThenK[v].add(treeMoreThenK[2 * v + 1].get(first2));
                    first2++;
                }
            }
            treeMoreThenK[v].add(maxValue);
        }

    }


    static class FastScanner {
        BufferedReader br;
        StringTokenizer stok;

        FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        String next() throws IOException {
            while (stok == null || !stok.hasMoreTokens()) {
                String s = br.readLine();
                if (s == null) {
                    return null;
                }
                stok = new StringTokenizer(s);
            }
            return stok.nextToken();
        }

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

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

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

        char nextChar() throws IOException {
            return (char) (br.read());
        }

        String nextLine() throws IOException {
            return br.readLine();
        }
    }
}