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.*;
import java.util.*;
import java.math.*;

public class utkarsh {

    InputStream is;
    PrintWriter out;
    
    int pt[], dp[][], h[], st[], en[], t, n, l = 20;
    ArrayList<Integer> a[], d[];
    
    void dfs(int s, int y){
        st[s] = t++;
        if(y > 0)   d[y].add(st[s]);
        h[s] = y;
        for(int x : a[s])   dfs(x, y+1);
        en[s] = t;
    }
    
    int play(int u, int p){
        if(p > h[u])    return -1;
        for(int i = l-1; i >= 0; i--){
            if(((p >> i) & 1) != 0) u = dp[u][i];
        }
        return u;
    }
    
    void init(){
        t = 0;
        st = new int[n];
        en = new int[n];
        pt = new int[n];
        h = new int[n];
        a = new ArrayList[n];
        d = new ArrayList[n];
        for(int i = 0; i < n; i++){
            a[i] = new ArrayList<>();
            d[i] = new ArrayList<>();
        }
    }
    
    int bs(ArrayList<Integer> arr, int x){
        int l, r, m;
        l = 0;
        r = arr.size() - 1;
        while(l <= r){
            m = l + r >> 1;
            if(arr.get(m) >= x)   r = m-1;
            else    l = m+1;
        }
        return r;
    }
    
    void solve(){
        //Enter code here utkarsh
        int i, j;
        n = ni();
        init();
        for(i = 0; i < n; i++){
            pt[i] = ni()-1;
            if(pt[i] != -1) a[pt[i]].add(i);
            else    d[0].add(i);
        }
        
        for(int x : d[0])   dfs(x, 0);
        
        dp = new int[n][l];
        for(i = 0; i < n; i++){
            dp[i][0] = pt[i];
            for(j = 1; j < l; j++)  dp[i][j] = -1;
        }
        for(j = 1; j < l; j++){
            for(i = 0; i < n; i++){
                if(dp[i][j-1] != -1){
                    dp[i][j] = dp[dp[i][j-1]][j-1];
                }
            }
        }
        
        int q = ni();
        while(q-- > 0){
            int u = ni() - 1;
            int p = ni();
            int dist = h[u];
            if(p > h[u]){
                out.print("0 ");
                continue;
            }
            u = play(u, p);
            out.print(bs(d[dist], en[u]) - bs(d[dist], st[u]) - 1 +" ");
        }
    }
    
    public static void main(String[] args) { new utkarsh().run();
    }
    void run(){ is = System.in; out = new PrintWriter(System.out); solve(); out.flush();
    }
    
    byte input[] = new byte[1024];
    int len = 0, ptr = 0;
    
    int readByte(){ if(ptr >= len){ ptr = 0; try{ len = is.read(input); }catch(IOException e){ throw new InputMismatchException(); } if(len <= 0){ return -1; } } return input[ptr++];
    }
    boolean isSpaceChar(int c){ return !( c >= 33 && c <= 126 ); 
    }
    int skip(){ int b = readByte(); while(b != -1 && isSpaceChar(b)){ b = readByte(); } return b;
    }
    
    char nc(){ return (char)skip();
    }
    String ns(){ int b = skip(); StringBuilder sb = new StringBuilder(); while(!isSpaceChar(b)){ sb.appendCodePoint(b); b=readByte(); } return sb.toString();
    }
    int ni(){ int n = 0,b = readByte(); boolean minus = false; while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')){ b = readByte(); } if(b == '-'){ minus = true; b = readByte(); } if(b == -1){ return -1; } while(b >= '0' && b <= '9'){ n = n * 10 + (b - '0'); b = readByte(); } return minus ? -n : n;
    }
    long nl(){ long n = 0L; int b = readByte(); boolean minus = false; while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')){ b = readByte(); } if(b == '-'){ minus = true; b = readByte(); } while(b >= '0' && b <= '9'){ n = n * 10 + (b - '0'); b = readByte(); } return minus ? -n : n;
    }
    double nd(){ return Double.parseDouble(ns());
    }
    float nf(){ return Float.parseFloat(ns());
    }
    int[] na(int n){ int a[] = new int[n]; for(int i = 0; i < n; i++){ a[i] = ni(); } return a;
    }
    char[] ns(int n){ char c[] = new char[n]; int i,b = skip(); for(i = 0; i < n; i++){ if(isSpaceChar(b)){ break; } c[i] = (char)b; b = readByte(); } return i == n ? c : Arrays.copyOf(c,i);
    }
}