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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int n, m;
int L[100005];
int R[100005];
int num[100005];
int treeL[100005];
int treeR[100005];
int name[100005];
int rec[100005];
int par[100005][20];
int pos[100005];
int tree[100005 + 10];
int ans[100005];
vector<int> ord;
vector<int> from[100005];
vector<pair<int, int> > a[100005];
queue<pair<int, int> > q;
map<string, int> names;
int getname(string s) {
  if (names.find(s) != names.end()) return names[s];
  int t = names.size() + 1;
  return names[s] = t;
}
void bfs() {
  int i, x, last, now;
  ord.push_back(0);
  rec[0] = ord.size() - 1;
  for (now = 0; now < from[0].size(); now++) {
    q.push({from[0][now], 0});
    treeL[now] = ord.size();
    while (!q.empty()) {
      x = q.front().first;
      last = q.front().second;
      q.pop();
      ord.push_back(x);
      rec[x] = ord.size() - 1;
      num[x] = now;
      par[x][0] = last;
      for (i = 1; i <= 18; i++) par[x][i] = par[par[x][i - 1]][i - 1];
      for (i = 0; i < from[x].size(); i++)
        if (from[x][i] != last) q.push({from[x][i], x});
    }
    treeR[now] = ord.size() - 1;
  }
}
int kth(int x, int val) {
  int i;
  for (i = 0; i <= 18; i++) {
    if (val & 1) x = par[x][i];
    val /= 2;
  }
  return x;
}
int sum(int x) {
  int ans = 0;
  while (x > 0) {
    ans += tree[x];
    x -= x & -x;
  }
  return ans;
}
void add(int x, int val) {
  while (x <= n + 5) {
    tree[x] += val;
    x += x & -x;
  }
}
int main() {
  int i, j, x, k, l, r, mid, t;
  string temp;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    cin >> temp >> x;
    name[i] = getname(temp);
    from[x].push_back(i);
    par[i][0] = x;
  }
  bfs();
  scanf("%d", &m);
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &x, &k);
    l = treeL[num[x]];
    r = treeR[num[x]];
    while (l <= r) {
      mid = (l + r) / 2;
      t = kth(ord[mid], k);
      if (rec[t] >= rec[x]) {
        if (rec[t] == rec[x]) L[i] = mid;
        r = mid - 1;
      } else
        l = mid + 1;
    }
    l = treeL[num[x]];
    r = treeR[num[x]];
    while (l <= r) {
      mid = (l + r) / 2;
      t = kth(ord[mid], k);
      if (rec[t] <= rec[x]) {
        if (rec[t] == rec[x]) R[i] = mid;
        l = mid + 1;
      } else
        r = mid - 1;
    }
    a[R[i]].push_back({L[i], i});
  }
  for (i = 1; i <= n; i++) {
    x = ord[i];
    if (pos[name[x]]) add(pos[name[x]], -1);
    pos[name[x]] = i;
    add(pos[name[x]], 1);
    for (j = 0; j < a[i].size(); j++)
      ans[a[i][j].second] = sum(i) - sum(a[i][j].first - 1);
  }
  for (i = 1; i <= m; i++) printf("%d\n", ans[i]);
}