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

@SuppressWarnings("unchecked")
public class BloodCousins {

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String[] splits;

        int n = Integer.parseInt(in.readLine());

        Graph relationships = new Graph(n);
        List<Integer> roots = new ArrayList<>();

        splits = in.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            int parent = Integer.parseInt(splits[i]) - 1;
            if (parent == -1)
                roots.add(i);
            else
                relationships.addUndirectedEdge(i, parent);
        }

        DFS dfs = new DFS(relationships.adj(), roots);

        ArrayList<Integer>[] level = (ArrayList<Integer>[]) new ArrayList[n];
        for (int i = 0; i < level.length; i++)
            level[i] = new ArrayList<>();

        for (int v = 0; v < n; v++)
            level[dfs.depth(v)].add(dfs.enter(v));

        for (int i = 0; i < level.length; i++)
            Collections.sort(level[i]);

        LCA lca = new LCA(relationships.adj(), roots);

        int m = Integer.parseInt(in.readLine());
        while (m-- > 0) {
            splits = in.readLine().split(" ");
            int v = Integer.parseInt(splits[0]) - 1;
            int p = Integer.parseInt(splits[1]);

            int a = lca.ancestor(v, p);
            out.print(a != -1 ? BinarySearch.count(level[dfs.depth(v)], dfs.enter(a), dfs.exit(a)) - 1 : 0);
            if (m > 0)
                out.print(" ");
        }
        out.flush();
    }

    @SuppressWarnings("unchecked")
    private static class Graph {

        private Collection<Integer>[] adj;

        public Graph(int N) {
            adj = (Collection<Integer>[]) new Collection[N];
            for (int i = 0; i < adj.length; i++)
                adj[i] = new ArrayList<>();
        }

        public void addDirectedEdge(int from, int to) {
            adj[from].add(to);
        }

        public void addUndirectedEdge(int v, int w) {
            addDirectedEdge(v, w);
            addDirectedEdge(w, v);
        }

        public Collection<Integer>[] adj() {
            return adj;
        }

        public Collection<Integer> adj(int v) {
            return adj[v];
        }

    }

    private static class DFS {

        private ArrayList<Integer> order;
        private int[] enter;
        private int[] exit;
        private int[] depth;

        public DFS(Collection<Integer>[] G, int s) {
            List<Integer> tmp = new ArrayList<>();
            tmp.add(s);
            dfs(G, tmp);
        }

        public DFS(Collection<Integer>[] G, List<Integer> S) {
            dfs(G, S);
        }

        private void dfs(Collection<Integer>[] G, List<Integer> S) {
            int N = G.length;

            order = new ArrayList<>();
            enter = new int[N];
            exit = new int[N];
            depth = new int[N];
            Arrays.fill(enter, -1);
            Arrays.fill(exit, -1);
            Arrays.fill(depth, Integer.MAX_VALUE);

            for (int s : S)
                dfs(s, 0, G);
        }

        public int count() {
            return order.size();
        }

        public boolean reachable(int v) {
            return enter[v] != -1;
        }

        public int enter(int v) {
            return enter[v];
        }

        public int exit(int v) {
            return exit[v];
        }

        public int depth(int v) {
            return depth[v];
        }

        public ArrayList<Integer> order() {
            return order;
        }

        private void dfs(int v, int depth, Collection<Integer>[] G) {
            if (enter[v] != -1)
                return;

            enter[v] = order.size();
            this.depth[v] = depth;
            order.add(v);
            for (int w : G[v])
                dfs(w, depth + 1, G);
            exit[v] = order.size() - 1;
        }

    }

    private static class LCA {

        private int[] level;
        private int[][] DP;
        private int[] cc;

        public LCA(Collection<Integer>[] tree, int root) {
            Collection<Integer> tmp = new ArrayList<>();
            tmp.add(root);
            lca(tree, tmp);
        }

        public LCA(Collection<Integer>[] tree, Collection<Integer> roots) {
            lca(tree, roots);
        }

        private void lca(Collection<Integer>[] forest, Collection<Integer> roots) {
            int N = forest.length;

            int[] parent = new int[N];
            Arrays.fill(parent, -1);
            for (int root : roots)
                parent[root] = root;

            level = new int[N];
            cc = new int[N];

            for (int root : roots)
                dfs(root, parent, root, forest);

            int max = Integer.MIN_VALUE;
            for (int i = 0; i < N; i++)
                max = Math.max(max, level[i]);

            int log = log2(max) + 1;
            DP = new int[N][log + 1];

            for (int i = 0; i < N; i++)
                DP[i][0] = parent[i];

            for (int j = 1; j <= log; j++) {
                for (int i = 0; i < N; i++)
                    DP[i][j] = DP[DP[i][j-1]][j-1];
            }
        }

        private int lca(int v, int w) {
            if (cc[v] != cc[w])
                return -1;

            if (level[v] < level[w])
                return lca(w, v);

            int log = log2(level[v]);

            for (int i = log; i >= 0; i--) {
                if (level[DP[v][i]] >= level[w])
                    v = DP[v][i];
            }

            for (int i = log; i >= 0; i--) {
                if (DP[v][i] != DP[w][i]) {
                    v = DP[v][i];
                    w = DP[w][i];
                }
            }

            return v;
        }

        private int ancestor(int v, int i) {
            if (level[v] < i)
                return -1;
            i = level[v] - i;
            for (int j = log2(level[v]); j >= 0; j--) {
                if (level[DP[v][j]] >= i)
                    v = DP[v][j];
            }
            return v;
        }

        private void dfs(int v, int[] parent, int cc, Collection<Integer>[] G) {
            for (int w : G[v]) {
                if (parent[w] == -1) {
                    parent[w] = v;
                    level[w] = level[v] + 1;
                    this.cc[w] = cc;
                    dfs(w, parent, cc, G);
                }
            }
        }

        private static int log2(int x) {
            return x != 0 ? (int) Math.ceil(Math.log(x) / Math.log(2)) : 0;
        }

    }

    private static class BinarySearch {

        public static <T> int floor(ArrayList<? extends Comparable<? super T>> a, T x) {
            int i = Collections.binarySearch(a, x);
            return i >= 0 ? i : -i - 2;
        }

        public static <T> int ceil(ArrayList<? extends Comparable<? super T>> a, T x) {
            int i = Collections.binarySearch(a, x);
            return i >= 0 ? i : -i - 1;
        }

        public static <T> int count(ArrayList<? extends Comparable<? super T>> a, T i, T j) {
            return floor(a, j) - ceil(a, i) + 1;
        }

    }

}