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.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.StringTokenizer;


public class TaskE {
    public static void main(String[] args) {
        InputStream inputStream;
        String str = null;
        if(str == null){
            inputStream = System.in;
        }else{
            inputStream = new ByteArrayInputStream(str.getBytes());
        }
        
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(1, in, out);
        out.close();
    }
    

    static class Solver {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int numPeople = in.nextInt();
            Person[] people = new Person[numPeople+1];
            
            HashMap<Integer, ArrayList<Integer>> levels = new HashMap<>();
            LinkedList<Person> roots = new LinkedList<>();
            
            
            for(int i=1;i<=numPeople;i++){
                people[i] = new Person();
                people[i].index = i;
            }
            
            for(int i=1;i<=numPeople;i++){
                people[i].parent = people[in.nextInt()];
                //if(people[i].parent != null)
                //System.out.println("Node " + i + " has parent " + people[i].parent.index);
                if(people[i].parent == null){
                    roots.add(people[i]);
                }else{
                    people[i].parent.children.add(people[i]);
                }
            }
            
            //preprocess
            int counter = 1;
            HashMap<Integer, Person> origIDtoNewID  = new HashMap<>();
            for(Person root : roots){
                LinkedList<Person> toVisit = new LinkedList<>();
                HashSet<Person> visited = new HashSet<>();
                toVisit.add(root);
                //System.out.println("Starting");
                while(!toVisit.isEmpty()){
                    
                    Person current = toVisit.getFirst();
                    if(visited.contains(current)){
                        if(current.children.isEmpty()){
                            toVisit.remove(current);
                            if(current.parent!=null){
                                current.parent.maxChild = Math.max(current.ID, current.maxChild);
                                //System.out.println(current.index+" " + current.parent.maxChild);
                            }
                        }else{
                            toVisit.addFirst(current.children.removeFirst());
                        }
                    }else{
                        current.ID = counter++;
                        current.maxChild = current.ID;
                        origIDtoNewID.put(current.ID, current);
                        //System.out.println("Mapping: " + current.index + " to "+ current.ID);
                        visited.add(current);
                        if(current.parent != null){
                            current.height = current.parent.height+1;
                        }
                        if(!levels.containsKey(current.height)){
                            levels.put(current.height, new ArrayList<>());
                        }
                        levels.get(current.height).add(current.ID);
                    }
                }
            }
            
            int numQueries = in.nextInt();
            
            StringBuilder answers = new StringBuilder();
            for(int query=0;query<numQueries;query++){
                Person target = people[in.nextInt()];
                int level = in.nextInt();
                
                //System.out.println(query+": looking at node " + target.index + " parent is " + (target.parent == null ? null : target.parent.index));
                if(level > target.height){
                    answers.append(0+" ");
                    continue;
                }
                
                //System.out.println("Searching: " + target.ID);
                int parentIndex = levels.get(target.height-level).get((Collections.binarySearch(levels.get(target.height-level), target.ID)+1)*-1-1);
                //System.out.println(levels.get(target.height-level));
                //System.out.println(parentIndex+" is parent");
                Person parent = people[origIDtoNewID.get(parentIndex).index];
                
                int left = parent.ID;
                int right = parent.maxChild+1;
                
                int l = Collections.binarySearch(levels.get(target.height), left);
                int r = Collections.binarySearch(levels.get(target.height), right);
                //System.out.println(left + " "+ right + " -> " + l + " " +r + " " + levels.get(target.height));
                
                if(l < 0){
                    l = (l+1)*-1;
                }
                if(r < 0){
                    r = (r+1)*-1;
                }
                //System.out.println(left + " "+ right + " -> " + l + " " +r);
                //System.out.println();
                answers.append(r-l-1);
                answers.append(" ");
            }
            
            System.out.println(answers);
        }
    }
    
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
 
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(next());
        }
        
        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}

class Person{
    Person parent;
    LinkedList<Person> children = new LinkedList<>();
    int ID;
    int index;
    int height = 0;
    int maxChild = 0;
}