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 kMax = 100010;
struct Query {
  int ql, qr, qi;
  Query(int _ql, int _qr, int _qi) { ql = _ql, qr = _qr, qi = _qi; }
  bool operator<(const Query &rq) const { return qr < rq.qr; }
};
int N, Q;
int si[kMax], di[kMax], lf[kMax], rg[kMax], dfn, max_dpt;
vector<int> tree[kMax], vsi[kMax], vlf[kMax], vrg[kMax];
int qvi[kMax], qki[kMax];
vector<Query> vq[kMax];
int res[kMax], f[kMax];
map<int, int> rm_pos;
void read(void);
void prep(void);
void soups_on(void);
void dfs(int, int);
void update(int, int);
int query_sum(int);
inline int low_bit(int i) { return i & (-i); }
int main() {
  ios::sync_with_stdio(false);
  read(), prep(), soups_on();
  return 0;
}
void read(void) {
  string str;
  int prn, id_cnt;
  map<string, int> name_id;
  cin >> N;
  id_cnt = 0;
  for (int i = 1; i <= N; ++i) {
    cin >> str >> prn;
    if (name_id.count(str) == 0) name_id[str] = id_cnt++;
    si[i] = name_id[str];
    tree[prn].push_back(i);
  }
  cin >> Q;
  for (int i = 0; i < Q; ++i) cin >> qvi[i] >> qki[i];
}
void prep(void) {
  int vi, ki, d, l, r;
  dfs(0, 0);
  for (int i = 0; i < Q; ++i) {
    vi = qvi[i], ki = qki[i], d = di[vi] + ki;
    if (d <= max_dpt) {
      l = lower_bound(vlf[d].begin(), vlf[d].end(), lf[vi]) - vlf[d].begin();
      r = lower_bound(vrg[d].begin(), vrg[d].end(), rg[vi]) - vrg[d].begin();
      vq[d].push_back(Query(l, r, i));
    }
  }
  for (int i = 1; i <= max_dpt; ++i) stable_sort(vq[i].begin(), vq[i].end());
}
void soups_on(void) {
  for (int i = 1; i <= max_dpt; ++i) {
    int p, q;
    p = q = 0;
    while (q < int(vq[i].size())) {
      Query &rq = vq[i][q];
      while (p < rq.qr) {
        if (rm_pos.count(vsi[i][p])) update(rm_pos[vsi[i][p]] + 1, -1);
        rm_pos[vsi[i][p]] = p;
        update(p + 1, 1);
        ++p;
      }
      res[rq.qi] = query_sum(rq.qr) - query_sum(rq.ql), ++q;
    }
    for (map<int, int>::iterator itr = rm_pos.begin(); itr != rm_pos.end();
         ++itr)
      update(itr->second + 1, -1);
    rm_pos.clear();
  }
  for (int i = 0; i < Q; ++i) cout << res[i] << "\n";
}
void dfs(int u, int lv) {
  di[u] = lv, vsi[lv].push_back(si[u]), vlf[lv].push_back(lf[u] = dfn), ++dfn;
  for (int i = 0; i < int(tree[u].size()); ++i) dfs(tree[u][i], lv + 1);
  vrg[lv].push_back(rg[u] = dfn), ++dfn, max_dpt = max(max_dpt, lv);
}
void update(int i, int dlt) {
  while (i < kMax) f[i] += dlt, i += low_bit(i);
}
int query_sum(int i) {
  int ret = 0;
  while (i > 0) ret += f[i], i -= low_bit(i);
  return ret;
}