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.*;

public class Program {

  static BufferedReader in;
  static PrintWriter out;
  static StringTokenizer tok = new StringTokenizer("");

  public static void main(String[] args) throws IOException {

    in = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(System.out);

    solve();
    out.close();
  }

  private static String readString() {
    while (!tok.hasMoreTokens()) {
      try {
        tok = new StringTokenizer(in.readLine());
      } catch (IOException e) {
        e.printStackTrace();
      }
    }
    return tok.nextToken();
  }

  private static int readInt() {
    return Integer.parseInt(readString());
  }

  private static double readDouble() {
    return Double.parseDouble(readString());
  }

  private static long readLong() {
    return Long.parseLong(readString());
  }


  static int timer = 0;
  static int[] tin;
  static int[] tout;
  static List<Integer>[] graph;
  static int[] dist;
  static int pointer = 0;
  static int[] renamedNodes;

  private static void solve() throws IOException {
    int n = readInt();
    String[] names = new String[n];
    graph = new ArrayList[n];
    for (int i = 0; i < n; i++) {
      graph[i] = new ArrayList<>();
    }
    tin = new int[n];
    tout = new int[n];
    dist = new int[n];
    renamedNodes = new int[n];
    Map<String, Integer> mappedNames = new HashMap<>();
    List<Integer> roots = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      names[i] = readString();
      mappedNames.put(names[i], i);
      int parent = readInt() - 1;
      if (parent > -1) {
        graph[parent].add(i);
      } else {
        roots.add(i);
      }
    }
    bfs(roots);
    for (int v : roots) {
      dfs(v, 0);
    }

    int q = readInt();
    Request[] requests = new Request[q];
    for (int i = 0; i < q; i++) {
      requests[i] = new Request(readInt() - 1, readInt(), i);
    }
    Arrays.sort(requests);
    int[] ans = new int[q];
    int[] lastSeen = new int[n];
    int[] temp = new int[n];
    Arrays.fill(temp, n);
    for (int i = n - 1; i >= 0; i--) {
      int oldIndex = renamedNodes[i];
      int value = mappedNames.get(names[oldIndex]);

      lastSeen[i] = temp[value];
      temp[value] = i;
    }

    SegmentTree tree = new SegmentTree(n + 1);
    Set<Integer> used = new HashSet<>();
    for (int i = 0; i < n; i++) {
      int oldIndex = renamedNodes[i];
      int value = mappedNames.get(names[oldIndex]);
      if (!used.contains(value)) {
        used.add(value);
        tree.addValue(0, 0, n + 1, i, 1);
      }
    }
    int pointer = 0;

    for (int left = 0; left < n; left++) {
      while (pointer < q && requests[pointer].left == left) {
        int sum = tree.getSum(0, 0, n + 1, left, requests[pointer].right + 1);
        ans[requests[pointer].index] = sum;
        pointer++;
      }
      tree.addValue(0, 0, n + 1, lastSeen[left], 1);
    }

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

    }


  }

  private static void bfs(List<Integer> start) {
    Deque<Integer> deque = new ArrayDeque<>();
    deque.addAll(start);
    while (!deque.isEmpty()) {
      int v = deque.pollFirst();
      renamedNodes[pointer++] = v;
      deque.addAll(graph[v]);
    }

  }

  private static void dfs(int v, int h) {
    tin[v] = timer++;
    dist[v] = h;
    for (int to : graph[v]) {
      dfs(to, h + 1);
    }
    tout[v] = timer;
  }

  static class Request implements Comparable<Request> {
    int v, k, index, left, right;

    public Request(int v, int k, int index) {
      this.v = v;
      this.k = k;
      this.index = index;
      this.left = find(v, k, true);
      this.right = find(v, k, false);
      if (left < 0 || right < 0) {
        left = 0;
        right = -1;
      }
    }

    @Override
    public int compareTo(Request o) {
      int t = Integer.compare(this.left, o.left);
      return t != 0 ? t : Integer.compare(this.right, o.right);
    }
  }

  static int find(int parent, int depth, boolean isLeft) {
    int left = 0;
    int right = tout.length - 1;
    int res = -1;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (dist[renamedNodes[mid]] < dist[parent] + depth) {
        left = mid + 1;
        continue;
      }
      if (dist[renamedNodes[mid]] > dist[parent] + depth) {
        right = mid - 1;
        continue;
      }
      if (isUpper(parent, renamedNodes[mid])) {
        res = mid;
        if (isLeft) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else {
        if (tin[parent] > tin[renamedNodes[mid]]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }
    return res;
  }

  static boolean isUpper(int a, int b) {
    return tin[a] < tin[b] && tout[a] >= tout[b];
  }

  static class SegmentTree {
    int n;
    int[] t;

    public SegmentTree(int n) {
      this.n = n;
      this.t = new int[4 * n];
    }

    int getSum(int idx, int l, int r, int L, int R) {
      if (l == L && r == R) {
        return t[idx];
      }
      int mid = (l + r) / 2;
      int res = 0;
      if (L < mid) {
        res += getSum(idx * 2 + 1, l, mid, L, Math.min(mid, R));
      }
      if (R > mid) {
        res += getSum(idx * 2 + 2, mid, r, Math.max(mid, L), R);
      }
      return res;
    }

    void addValue(int idx, int l, int r, int index, int value) {
      if (r - l == 1) {
        t[idx] = value;
        return;
      }
      int mid = (l + r) / 2;
      if (index < mid) {
        addValue(idx * 2 + 1, l, mid, index, value);
      } else {
        addValue(idx * 2 + 2, mid, r, index, value);
      }
      t[idx] = t[idx * 2 + 1] + t[idx * 2 + 2];
    }


  }

}