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;
template <typename T>
void read(T &x);
template <typename T>
void write(T x);
template <typename T>
void writesp(T x);
template <typename T>
void writeln(T x);
const int N = 1e5 + 5;
vector<int> que[N], vec[N];
map<string, int> Map;
int n, name[N], Col, root[N], h, m, ans[N], kk[N], rt[N], Md[N];
string s;
namespace seg {
set<int> st[N << 3];
int id[N << 5], lc[N << 5], rc[N << 5], cnt, rem;
inline void update(int &p, int l, int r, int k, int val) {
  if (!p) p = ++cnt;
  if (l == r) {
    if (!id[p]) id[p] = ++rem;
    if (st[id[p]].find(val) == st[id[p]].end()) st[id[p]].insert(val);
    return;
  }
  int mid = l + r >> 1;
  if (k <= mid)
    update(lc[p], l, mid, k, val);
  else
    update(rc[p], mid + 1, r, k, val);
}
inline void merge(int &p, int q) {
  if (!p || !q) return (void)(p += q);
  if (id[p] || id[q]) {
    if (!id[p] || !id[q]) return (void)(id[p] += id[q]);
    if (st[id[p]].size() < st[id[q]].size()) swap(id[p], id[q]);
    for (set<int>::iterator it = st[id[q]].begin(); it != st[id[q]].end();
         it++) {
      if (st[id[p]].find((*it)) != st[id[p]].end()) continue;
      st[id[p]].insert((*it));
    }
    st[id[q]].clear();
    return;
  }
  merge(lc[p], lc[q]);
  merge(rc[p], rc[q]);
}
inline int query(int p, int l, int r, int k) {
  if (!p) return 0;
  if (l == r) return id[p] ? st[id[p]].empty() ? 0 : st[id[p]].size() : 0;
  int mid = l + r >> 1;
  if (k <= mid)
    return query(lc[p], l, mid, k);
  else
    return query(rc[p], mid + 1, r, k);
}
}  // namespace seg
inline void dfs(int x, int deep) {
  Md[x] = deep;
  if (x) seg::update(rt[x], 1, n, Md[x], name[x]);
  int ver;
  for (vector<int>::iterator it = vec[x].begin(); it != vec[x].end(); it++) {
    ver = (*it);
    dfs(ver, deep + 1);
    Md[x] = max(Md[x], Md[ver]);
    seg::merge(rt[x], rt[ver]);
  }
  int id;
  for (vector<int>::iterator it = que[x].begin(); it != que[x].end(); it++) {
    id = (*it);
    if (kk[id] + deep > Md[x]) continue;
    ans[id] = seg::query(rt[x], 1, n, kk[id] + deep);
  }
}
int main() {
  read(n);
  for (register int i = 1, x; i <= n; i++) {
    s = "";
    char wn = getchar();
    while (wn < 'a' || wn > 'z') wn = getchar();
    while (wn >= 'a' && wn <= 'z') s += wn, wn = getchar();
    if (Map.find(s) == Map.end()) Map[s] = ++Col;
    name[i] = Map[s];
    read(x);
    vec[x].push_back(i);
  }
  read(m);
  for (register int i = 1, x; i <= m; i++) {
    read(x);
    read(kk[i]);
    que[x].push_back(i);
  }
  dfs(0, 0);
  for (register int i = 1; i <= m; i++) writeln(ans[i]);
}
template <typename T>
void read(T &x) {
  x = 0;
  int t = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') t = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= t;
}
template <typename T>
void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x <= 9) {
    putchar(x + '0');
    return;
  }
  write(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void writesp(T x) {
  write(x);
  putchar(' ');
}
template <typename T>
void writeln(T x) {
  write(x);
  putchar('\n');
}