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 maxx = 2e5 + 20, mxlg = 20;
int n, mq[maxx], qu[maxx], id[maxx], ans[maxx], h[maxx], par[maxx][mxlg], m,
    lh[maxx], rh[maxx];
pair<int, int> ans_seg[maxx];
queue<int> q;
vector<int> adj[maxx], v;
bool vis[maxx];
vector<pair<pair<int, int>, int> > segs;
map<string, int> mm;
string str[maxx];
int st[4 * maxx + 10];
void modify(int x, int k, int id = 1, int l = 1, int r = n + 1) {
  st[id] += k;
  if (l + 1 == r) return;
  int mid = (l + r) / 2;
  if (x < mid)
    modify(x, k, id * 2, l, mid);
  else
    modify(x, k, id * 2 + 1, mid, r);
}
int get_sum(int x, int y, int id = 1, int l = 1, int r = n + 1) {
  if (x >= r || l >= y) return 0;
  if (x <= l && r <= y) return st[id];
  int mid = (l + r) / 2;
  return get_sum(x, y, id * 2, l, mid) + get_sum(x, y, id * 2 + 1, mid, r);
}
int find_par(int u, int ert) {
  for (int i = mxlg - 1; i >= 0; i--)
    if (ert & (1 << i)) u = par[u][i];
  return u;
}
pair<int, int> getAB(int x1, int y1) {
  int f = h[x1] + y1;
  if (lh[f] == 0) return make_pair(-1, -2);
  int l = lh[f], r = rh[f] + 1;
  while (l + 1 != r) {
    int mid = (l + r) / 2;
    if (id[find_par(v[mid], y1)] <= id[x1])
      l = mid;
    else
      r = mid;
  }
  if (id[find_par(v[l], y1)] != id[x1])
    return make_pair(-1, -1);
  else
    return make_pair(v[l], y1);
}
int main() {
  int co = 0;
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  h[0] = -1;
  qu[0] = -1;
  for (int i = 1; i <= n; i++) {
    int g;
    string ss;
    cin >> ss >> g;
    str[i] = ss;
    adj[i].push_back(g);
    adj[g].push_back(i);
  }
  q.push(0);
  v.push_back(0), vis[0] = true, id[0] = 0;
  while (q.size()) {
    int x = q.front();
    q.pop();
    for (int y : adj[x]) {
      if (!vis[y]) {
        vis[y] = true, v.push_back(y), id[y] = v.size() - 1, q.push(y),
        h[y] = h[x] + 1;
        if (!lh[h[y]])
          lh[h[y]] = id[y];
        else
          lh[h[y]] = min(lh[h[y]], id[y]);
        if (!rh[h[y]])
          rh[h[y]] = id[y];
        else
          rh[h[y]] = max(rh[h[y]], id[y]);
        par[y][0] = x;
      }
    }
  }
  for (int i = 0; i < v.size(); i++) {
    if (mm.find(str[v[i]]) == mm.end()) mm[str[v[i]]] = co++;
    qu[i] = mm[str[v[i]]];
  }
  for (int i = 1; i < mxlg; i++) {
    for (int j = 1; j <= n; j++) {
      par[j][i] = par[par[j][i - 1]][i - 1];
    }
  }
  cin >> m;
  for (int i = 0; i < m; i++) {
    int ap, bp, x;
    cin >> ap >> bp;
    pair<int, int> w = getAB(ap, bp);
    int a = w.first, b = w.second;
    if (a == -1) {
      ans_seg[i] = w;
      continue;
    }
    if (h[a] < b) continue;
    x = ap;
    int l = 1, r = id[a] + 1;
    while (l + 1 != r) {
      int mid = (l + r) / 2;
      if (h[v[mid]] < h[a] || find_par(v[mid], b) != x)
        l = mid;
      else
        r = mid;
    }
    int s = l;
    l = id[a], r = n + 1;
    int e = id[a];
    ans_seg[i] = make_pair(s + 1, e + 1);
  }
  for (int i = 0; i < m; i++)
    if (ans_seg[i].first != -1)
      segs.push_back(
          make_pair(make_pair(ans_seg[i].second, ans_seg[i].first), i));
  sort(segs.begin(), segs.end());
  int p = 0;
  fill(mq, mq + n + 1, -1);
  for (int i = 1; i <= n + 1; i++) {
    while (p < segs.size() && segs[p].first.first <= i) {
      ans[segs[p].second] = get_sum(segs[p].first.second, segs[p].first.first);
      p++;
    }
    modify(i, 1);
    if (mq[qu[i]] != -1) modify(mq[qu[i]], -1);
    mq[qu[i]] = i;
  }
  for (int i = 0; i < m; i++) cout << ans[i] << endl;
  cout << "\n";
  return 0;
}