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.*;
import java.io.*;
public class BloodCousins
{
    static ArrayList<ArrayList<Integer>> v = new ArrayList<ArrayList<Integer>>();
    static ArrayList<ArrayList<Integer>> level = new ArrayList<ArrayList<Integer>>();
    static int dp[][] = new int[100010][18];
    static int depth [] = new int [100001];
    static int start [] = new int [100001];
    static int finish[] = new int [100001];
    static int time = 0;
    static int N , Q;
    public static void main(String[]args)
    {
        InputReader1 sc = new InputReader1(System.in);
        N = sc.nextInt();
        for(int i=0;i<=100010;i++)
        {
            v.add(new ArrayList<Integer>());
            level.add(new ArrayList<Integer>());
        }
        for(int i = 1 ; i <= N ; i++)
        {
            int parent = sc.nextInt();
            v.get(parent).add(i);
            for(int j = 0 ; j < 18 ; j++)
                dp[i][j] = -1;
        }
        dfs(0,1,-1);
        preprocess();
        Q = sc.nextInt();
        for(int i=1;i<=N;i++)
        {
            Collections.sort(level.get(i));
        }
        StringBuilder output = new StringBuilder();
        while(Q-->0)
        {
            int node = sc.nextInt(), k = sc.nextInt();
            int anc = ancestor(node,k);
            output.append(solve(anc,k)-1).append(" ");
        }
        System.out.println(output);
    }

    static int ancestor(int node , int k)
    {
        while(k>0)
        {
            int lim = (int)(Math.log(k)/Math.log(2)); // Nearest power of 2 <= k
            node = dp[node][lim]; // node = 2^limith ancestor of node
            if(node==-1) return -1;
            k-=(1<<lim); 
        } 
        return node;
    }

    static int solve(int node ,int dist)
    {
        if(node<=0)return 1;
        if(dist+depth[node]>=N)return 1;
        return upper_bound(level.get(dist+depth[node]) , finish[node])
             - lower_bound(level.get(dist+depth[node]) , start[node]) ;
    }

    static int upper_bound(ArrayList<Integer> x , int val)
    {
        // Returns first index > val
        int l = 0;
        int h = x.size()-1;
        if(h==-1)return 0;
        if(x.get(h)<=val) return h+1;
        if(x.get(0)>val)return 0;
        while(l!=h)
        {
            int mid = (l+h) / 2;
            if(x.get(mid)>val)
                h = mid;
            else
                l = mid+1;
        }
        if(l-1>=0 && x.get(l-1) > val)return l-1;
        else if(x.get(l)<=val) return x.size();
        else return l;
    }

    static int lower_bound(ArrayList<Integer> x , int val)
    {
        // Returns first index with value >= val
        int l = 0;
        int h = x.size()-1;
        if(h==-1)return 0;
        if(x.get(h) < val) return h+1;
        if(x.get(0) >=val) return 0;
        while(l!=h)
        {
            int mid = (l+h) / 2;
            if(x.get(mid)>=val)
                h = mid;
            else
                l = mid + 1;
        }
        if(x.get(l)<val) return x.size();
        else return l;
    }

    static void preprocess()
    {
        for(int j=1;j<18;j++)
        {
            for(int i=1;i<=N;i++)
            {
                if(dp[i][j-1]!=-1)
                    dp[i][j] = dp[dp[i][j-1]][j-1];
            }
        }
    }

    static void dfs(int node , int lvl , int par)
    {
        start[node] = ++time;
        level.get(lvl).add(start[node]);
        depth[node] = lvl;  
        dp[node][0] = par;
        for(int next : v.get(node))
            dfs(next,lvl+1,node);
        finish[node]= time;
    }
}
class InputReader1 
{

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

    public InputReader1(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() {
        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 & 15;
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

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

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

    public String nextLine() {
        int c = read();
        //while (c != '\n' && c != '\r' && c != '\t' && c != -1)
        //c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (c != '\n' && c != '\r' && c != '\t' && c != -1);
        return res.toString();
    }

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

}