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.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class E208 {
    int ans[];
    int level[];
    int index[];
    int cnt[];
    Map<Integer, List<Integer>> pp;
    Map<Integer, Set<Integer>> edgs;
    int base = 0;

    int dfs(int d, int depth) {
        int size = 1;
        index[d] = base++;
        level[d] = depth;
        pp.get(depth).add(index[d]);
        for (int v : edgs.get(d)) {
            size += dfs(v, depth + 1);
        }
        cnt[d] = size;
        return size;
    }

    public void solve(Scanner cin, PrintWriter cout) {
        int n = cin.nextInt();
        edgs = new HashMap<Integer, Set<Integer>>();
        pp = new HashMap<Integer, List<Integer>>();
        int pre [] [] = new int [18][n];
        for (int i = 0; i < n; i++) {
            edgs.put(i, new HashSet<Integer>());
            pp.put(i, new ArrayList<Integer>());
        }
        for (int i = 0; i < n; i++) {
            pre[0][i] = cin.nextInt() - 1;
            if (pre[0][i] >= 0)
                edgs.get(pre[0][i]).add(i);
        }
        for (int i = 0; i < n; i++) 
            for (int j = 1; j < 18; j++)
                if( pre[j-1][i] >= 0 ) {
                    pre[j][i] = pre[j - 1][pre[j - 1][i]];
                }else{
                    pre[j][i] = -2;
                }

        level = new int[n];
        cnt = new int[n];
        index = new int[n];
        for (int i = 0; i < n; i++) {
            if (pre[0][i] < 0) {
                dfs(i, 0);
            }
        }
        int q = cin.nextInt();
        ans = new int[q];
        Map<Long,Integer> ok = new HashMap<Long,Integer>();
        for (int i = 0; i < q; i++) {
            int node = cin.nextInt() - 1;
            int bnode = node;
            int le = cin.nextInt();
            long key = node * 1000000 + le;
            if( ok.containsKey(key)){
                ans[i] = ok.get(key);
                continue;
            }
            for(int j=0 ; j < 18 ; j ++){
                if( (le&(1<<j) )> 0 && node >= 0){
                    node = pre[j][node];
                }
            }

            if (node < 0 ) {
                ans[i] = 0;
            } else {
                List<Integer> ns = pp.get(level[bnode]);
//              System.out.println(bnode);
                int min = index[node];
                int max = index[node] + cnt[node] - 1;
//               System.out.println(min + " " + max + " " + ns);
                int beg = -(1 + Collections.binarySearch(ns, min));
                int end = Collections.binarySearch(ns, max);
//               System.out.println(beg + " " + end);
                ans[i] = end >= 0 ? end - beg : -(1 + end) - beg - 1;
            }
            ok.put(key,ans[i]);
        }
        for (int i = 0; i < q; i++) {
            cout.print(ans[i]);
            if (i == q - 1) {
                cout.print("\n");
            } else {
                cout.print(" ");
            }
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        // ArrayList list= new ArrayList<Integer>();
        // list.add(1);
        // list.add(5);
        // list.add(6);
        // list.add(7);
        // list.add(9);
        // list.add(13);
        // list.add(37);
        // list.add(78);
        // System.out.println( -(1+ Collections.binarySearch(list, 2)));
        // System.out.println( -(Collections.binarySearch(list,10) + 1 ));
        // long beg = System.currentTimeMillis();
//      E208 solution = new E208();
//      Scanner cin = new Scanner(new FileInputStream("a.txt"));
//      PrintWriter cout = new PrintWriter(new FileOutputStream("a.ans"));
//      solution.solve(cin, cout);
//      cin.close();
//      cout.close();

         E208 solution = new E208();
         Scanner cin = new Scanner(System.in);
         PrintWriter cout = new PrintWriter(System.out);
         solution.solve(cin, cout);
         cin.close();
         cout.close();
    }
}