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.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        int n;
        int[][] parent;
        ArrayList<Integer>[] adjList;
        int[] tin;
        int[] tout;
        int[] dist;
        ArrayList<Integer>[] distance;
        boolean[] mrk;
        int T;

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            n = in.nextInt();
            parent = new int[25][n + 1];
            for (int i = 0; i < 25; i++) {
                Arrays.fill(parent[i], -1);
            }

            adjList = new ArrayList[n + 1];
            tin = new int[n + 1];
            tout = new int[n + 1];
            dist = new int[n + 1];
            mrk = new boolean[n + 1];
            distance = new ArrayList[n + 1];
            T = 0;
            for (int i = 0; i <= n; i++) {
                adjList[i] = new ArrayList<Integer>();
                distance[i] = new ArrayList<Integer>();
            }

            for (int i = 0; i < n; i++) {
                int x = in.nextInt();
                parent[0][i] = x - 1;
                if (x - 1 >= 0) adjList[x - 1].add(i);
            }

            for (int i = 0; i < n; i++) {
                if (parent[0][i] == -1) {
                    dfs(i, 0);
                }
            }

            for (int i = 0; i < 24; i++) {
                for (int x = 0; x < n; x++) {
                    if (parent[i][x] == -1) parent[i + 1][x] = -1;
                    else parent[i + 1][x] = parent[i][parent[i][x]];
                }
            }

            int m = in.nextInt();
            while (m-- > 0) {
                int v = in.nextInt() - 1;
                int p = in.nextInt();

                int par = findParent(v, p);
                if (par == -1) {
                    out.print(0 + " ");
                    continue;
                }

                int x = tin[par];
                int y = tout[par];

                int fd = dist[par] + p;
                if (fd >= n) {
                    out.print(0 + " ");
                    continue;
                }
                int tx = Collections.binarySearch(distance[fd], x);
                int ty = Collections.binarySearch(distance[fd], y);
                tx *= -1;
                tx -= 2;
                ty *= -1;
                ty -= 2;
//            out.println(v+ " " + p + " " + par + " " + fd + " " + tx + " " + ty);
                out.print((ty - tx - 1) + " ");
            }
        }

        private void dfs(int u, int d) {
            mrk[u] = true;
            tin[u] = ++T;
            dist[u] = d;
            distance[d].add(tin[u]);
            for (int x : adjList[u]) {
                if (!mrk[x]) dfs(x, d + 1);
            }
            tout[u] = ++T;
        }

        private int findParent(int v, int p) {
            while (p > 0) {
                int raise_by = (int) (Math.log(p) / Math.log(2));
                v = parent[raise_by][v];
                p = p - (1 << raise_by);
                if (v == -1) return v;
            }
            return v;
        }

    }

    static class FastScanner {
        private BufferedReader bufferedReader;
        private StringTokenizer stringTokenizer;

        public FastScanner(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
        }

        public String next() {
            if (stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return stringTokenizer.nextToken();
        }

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

    }
}