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;
const int N = 200010;
string s;
map<string, int> mp;
int n, Q, x, y, tot, skip, cnt, rts, id[N], fa[N], rt[N], ans[N], sz[N];
int son[N], d[N], h[N], to[N << 1], nxt[N << 1];
set<int> S[N];
struct P {
  int x, y;
};
vector<P> ve[N];
void add(int u, int v) {
  to[++cnt] = v;
  nxt[cnt] = h[u];
  h[u] = cnt;
}
void dfs(int x) {
  d[x] = d[fa[x]] + 1;
  sz[x] = 1;
  for (int i = h[x], k; i; i = nxt[i]) {
    dfs(k = to[i]);
    sz[x] += sz[k];
    if (sz[k] > sz[son[x]]) son[x] = k;
  }
}
void get(int x, int op) {
  if (op)
    S[d[x]].insert(id[x]);
  else
    S[d[x]].erase(id[x]);
  for (int i = h[x], k; i; i = nxt[i])
    if ((k = to[i]) != skip) get(k, op);
}
void work(int x, int op) {
  for (int i = h[x], k; i; i = nxt[i])
    if ((k = to[i]) != son[x]) work(k, 1);
  if (son[x]) work(son[x], 0), skip = son[x];
  get(x, 1);
  skip = 0;
  int ed = ve[x].size() - 1;
  for (int i = (0); i <= (ed); i++)
    ans[ve[x][i].x] = S[d[x] + ve[x][i].y].size();
  if (op) get(x, 0);
}
int main() {
  scanf("%d", &n);
  for (int i = (1); i <= (n); i++) {
    cin >> s >> fa[i];
    if (mp.find(s) != mp.end())
      id[i] = mp[s];
    else
      mp[s] = id[i] = ++tot;
    if (!fa[i])
      rt[++rts] = i;
    else
      add(fa[i], i);
  }
  scanf("%d", &Q);
  for (int i = (1); i <= (Q); i++)
    scanf("%d%d", &x, &y), ve[x].push_back((P){i, y});
  for (int i = (1); i <= (rts); i++) dfs(rt[i]), work(rt[i], 1);
  for (int i = (1); i <= (Q); i++) printf("%d\n", ans[i]);
  return 0;
}