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.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

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

    static class EBloodCousins {
        int curDepth = -1;
        int vv = 0;
        int[] newV;
        int[] height;
        int[] size;
        int[][] lca;
        ArrayList<Integer>[] adj;
        ArrayList<Integer>[] depth;

        public void solve(int testNumber, InputReader c, OutputWriter w) {
            int n = c.readInt();
            int[] a = c.readIntArray(n);
            adj = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                adj[i] = new ArrayList<>();
            }
            for (int i = 0; i < n; i++) {
                if (a[i] != 0) {
                    adj[i].add(a[i] - 1);
                    adj[a[i] - 1].add(i);
                }
            }
            depth = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                depth[i] = new ArrayList<>();
            }
            lca = new int[n][20];
            for (int i = 0; i < n; i++) {
                Arrays.fill(lca[i], -1);
            }
            newV = new int[n];
            height = new int[n];
            size = new int[n];

            for (int i = 0; i < n; i++) {
                if (a[i] == 0) {
                    dfs_(i, -1, curDepth + 1);
                }
            }

            int m = c.readInt();
            while (m-- > 0) {
                int v = newV[c.readInt() - 1], p = c.readInt();
                int ances = binaryLift(v, p);
                if (ances != -1) {
                    int l = ances, r = ances + size[ances] - 1;
                    w.print(ans_(height[v], l, r), "");
                } else {
                    w.print("0 ");
                }
            }
            w.printLine();
        }

        private int ans_(int dep, int l, int r) {
            int indL = -1, indR = -1;
            int ll = 0, rr = depth[dep].size() - 1;
            while (ll <= rr) {
                int mid = ll + rr >> 1;
                if (depth[dep].get(mid) >= l) {
                    indL = mid;
                    rr = mid - 1;
                } else {
                    ll = mid + 1;
                }
            }
            ll = 0;
            rr = depth[dep].size() - 1;
            while (ll <= rr) {
                int mid = ll + rr >> 1;
                if (depth[dep].get(mid) <= r) {
                    indR = mid;
                    ll = mid + 1;
                } else {
                    rr = mid - 1;
                }
            }
            return indR - indL;
        }

        private int binaryLift(int x, int dist) {
            for (int i = 19; i >= 0 && x != -1; i--) {
                if ((dist & (1 << i)) > 0) {
                    x = lca[x][i];
                }
            }
            return x;
        }

        private int dfs_(int x, int p, int dist) {
            curDepth = Math.max(curDepth, dist);
            newV[x] = vv++;
            int v = newV[x];
            depth[dist].add(v);
            height[v] = dist;
            if (p != -1) {
                lca[v][0] = newV[p];
            }
            for (int i = 1; i < 20; i++) {
                if (lca[v][i - 1] != -1) {
                    lca[v][i] = lca[lca[v][i - 1]][i - 1];
                }
            }
            for (int xx : adj[x]) {
                if (xx != p) {
                    size[v] += dfs_(xx, x, dist + 1);
                }
            }
            size[v]++;
            return size[v];
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int[] readIntArray(int size) {
            int[] array = new int[size];
            for (int i = 0; i < size; i++) {
                array[i] = readInt();
            }
            return array;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void printLine() {
            writer.println();
        }

        public void close() {
            writer.close();
        }

    }
}