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.util.List;
import java.io.IOException;
import java.util.TreeMap;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Collections;
import java.io.InputStream;

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

class TaskE {
    ArrayList<Integer>[] A;
    int idx;
    int[] newId;
    int[] oldId;
    int[] subTree;
    int[] L;
    int[] nameIdx;
    ArrayList<Integer>[] level;
    ArrayList<Interval> Q;

	public void solve(int testNumber, InputReader in, PrintWriter out) {
        int N = in.nextInt();

        A = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++)
            A[i] = new ArrayList<Integer>();
        nameIdx = new int[N + 1];
        TreeMap<String, Integer> names = new TreeMap<String, Integer>();
        int crtNameIdx = 0;

        boolean[] root = new boolean[N + 1];
        for(int i = 1; i <= N; i++) {
            String s = in.nextString();
            if(names.containsKey(s))
                nameIdx[i] = names.get(s);
            else {
                crtNameIdx++;
                names.put(s, crtNameIdx);
                nameIdx[i] = crtNameIdx;
            }
            int t = in.nextInt();
            if(t == 0)
                root[i] = true;
            else
                A[t].add(i);
        }

        newId = new int[N + 1];
        oldId = new int[N + 1];
        subTree = new int[N + 1];
        L = new int[N + 1];
        idx = 0;
        level = new ArrayList[N + 1];
        for(int i = 0; i < N + 1; i++)
            level[i] = new ArrayList<Integer>();
        for(int i = 1; i <= N; i++)
            if(root[i])
                dfs(i, 0);

        int M = in.nextInt();
        Q = new ArrayList<Interval>();
        for(int i = 0; i < M; i++) {
            int v = in.nextInt();
            int k = in.nextInt();

            int id = newId[v];
            int lowLvl = L[id] + k;


            if(lowLvl > N)
                continue;

            int lower = Integer.MAX_VALUE;
            int st = 0;
            int dr = level[lowLvl].size() - 1;
            int m;
            while(st <= dr) {
                m = (st + dr) / 2;
                if(level[lowLvl].get(m) < id + 1)
                    st = m + 1;
                else if(level[lowLvl].get(m) > id + subTree[id] - 1)
                    dr = m - 1;
                else {
                    lower = Math.min(lower, m);
                    dr = m - 1;
                }
            }

            int upper = -1;
            st = 0;
            dr = level[lowLvl].size() - 1;
            while(st <= dr) {
                m = (st + dr) / 2;
                if(level[lowLvl].get(m) < id + 1)
                    st = m + 1;
                else if(level[lowLvl].get(m) > id + subTree[id] - 1)
                    dr = m - 1;
                else {
                    upper = Math.max(upper, m);
                    st = m + 1;
                }
            }

            if(upper != -1)
                Q.add(new Interval(lower, upper, lowLvl, i));
        }

        Collections.sort(Q);

        int[] ans = new int[M + 1];
        int[] count = new int[N + 1];
        int dr = -1;
        int st = -1;
        int num = 0;
        for(int i = 0; i < Q.size(); i++) {
            if(i > 0 && Q.get(i).level != Q.get(i - 1).level) {
                while(st <= dr) {
                    if(st >= 0) {
                        int crt = level[Q.get(i - 1).level].get(st);
                        int id = oldId[crt];
                        int nameid = nameIdx[id];
                        count[nameid]--;
                        if(count[nameid] == 0)
                            num--;
                    }
                    st++;
                }
                st = -1;
                dr = -1;
                num = 0;
            }

            Interval e = Q.get(i);
            while(dr < e.right) {
                dr++;
                int crt = level[e.level].get(dr);
                int id = oldId[crt];
                int nameid = nameIdx[id];
                count[nameid]++;
                if(count[nameid] == 1)
                    num++;
            }

            while(dr > e.right) {
                int crt = level[e.level].get(dr);
                int id = oldId[crt];
                int nameid = nameIdx[id];
                count[nameid]--;
                if(count[nameid] == 0)
                    num--;
                dr--;
            }

            while(st < e.left) {
                if(st >= 0) {
                    int crt = level[e.level].get(st);
                    int id = oldId[crt];
                    int nameid = nameIdx[id];
                    count[nameid]--;
                    if(count[nameid] == 0)
                        num--;
                }
                st++;
            }

            while(st > e.left) {
                st--;
                int crt = level[e.level].get(st);
                int id = oldId[crt];
                int nameid = nameIdx[id];
                count[nameid]++;
                if(count[nameid] == 1)
                    num++;
            }

            ans[e.idx] = num;
        }

        for(int i = 0; i < M; i++)
            out.println(ans[i]);

	}

    private int dfs(int node, int lvl) {
        int crt = ++idx;
        newId[node] = crt;
        L[crt] = lvl;
        oldId[crt] = node;
        level[lvl].add(crt);
        subTree[crt] = 1;
        for(Integer x : A[node])
            subTree[crt] += dfs(x, lvl + 1);
        return subTree[crt];
    }

    private class Interval implements Comparable<Interval> {
        public int left;
        public int right;
        public int level;
        public int idx;

        private Interval(int left, int right, int level, int idx) {
            this.left = left;
            this.right = right;
            this.level = level;
            this.idx = idx;
        }

        public int compareTo(Interval o) {
            if(level != o.level)
                return level - o.level;
            if(right != o.right)
                return right - o.right;
            if(left != o.left)
                return left - o.left;
            return idx - o.idx;
        }
    }
}

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

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

    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 nextInt() {
        return Integer.parseInt(nextString());
    }

    public String nextString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuffer res = new StringBuffer();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    private boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    }