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>
const int inf = 0x3f3f3f3f, Inf = 0x7fffffff;
const long long INF = 0x7fffffffffffffff;
const double eps = 1e-10;
unsigned int seed = 19260817;
const unsigned int _RAND_MAX_ = 4294967295u;
__inline__ __attribute__((always_inline)) unsigned int Rand() {
  return seed = seed * 998244353u + 1000000007u;
}
template <typename _Tp>
_Tp gcd(const _Tp &a, const _Tp &b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp abs(const _Tp &a) {
  return a > 0 ? a : -a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp max(const _Tp &a, const _Tp &b) {
  return a < b ? b : a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp min(const _Tp &a, const _Tp &b) {
  return a < b ? a : b;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmax(_Tp &a, const _Tp &b) {
  (a < b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmin(_Tp &a, const _Tp &b) {
  (a > b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) bool _cmp(const _Tp &a,
                                                    const _Tp &b) {
  return abs(a - b) <= eps;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void read(_Tp &x) {
  register char ch(getchar());
  bool f(false);
  while (ch < 48 || ch > 57) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (ch >= 48 && ch <= 57)
    x = (((x << 2) + x) << 1) + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
__inline__ __attribute__((always_inline)) int read_str(char *s) {
  register char ch(getchar());
  while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
  register char *tar = s;
  *tar = ch, ch = getchar();
  while (ch != ' ' && ch != '\r' && ch != '\n' && ch != EOF)
    *(++tar) = ch, ch = getchar();
  return tar - s + 1;
}
const int N = 100005;
struct edge {
  int v, nxt;
} c[N];
int front[N], cnt;
__inline__ __attribute__((always_inline)) void add(const int &u, const int &v) {
  c[++cnt] = (edge){v, front[u]}, front[u] = cnt;
}
std::string s[N], t[N];
int a[N];
int Fa[N];
std::vector<std::pair<int, int> > v[N];
int dep[N], siz[N], son[N];
void _(int x) {
  siz[x] = 1;
  for (int i = front[x]; i; i = c[i].nxt) {
    dep[c[i].v] = dep[x] + 1;
    _(c[i].v);
    siz[x] += siz[c[i].v];
    if (siz[c[i].v] > siz[son[x]]) {
      son[x] = c[i].v;
    }
  }
}
int Son;
std::unordered_map<int, int> mp[N];
int ans[N];
void Upd(int x) {
  ++mp[dep[x]][a[x]];
  for (int i = front[x]; i; i = c[i].nxt) {
    if (c[i].v != Son) {
      Upd(c[i].v);
    }
  }
}
void del(int x) {
  --mp[dep[x]][a[x]];
  if (!mp[dep[x]][a[x]]) {
    mp[dep[x]].erase(mp[dep[x]].find(a[x]));
  }
  for (int i = front[x]; i; i = c[i].nxt) {
    del(c[i].v);
  }
}
void dfs(int x, bool keep) {
  for (int i = front[x]; i; i = c[i].nxt) {
    if (c[i].v != son[x]) {
      dfs(c[i].v, 0);
    }
  }
  if (son[x]) dfs(son[x], 1), Son = son[x];
  Upd(x), Son = 0;
  for (auto it : v[x]) {
    if (it.first <= 100000) {
      ans[it.second] = mp[it.first].size();
    }
  }
  if (!keep) del(x);
}
int main() {
  int n, x;
  read(n);
  for (int i = 1; i <= n; ++i) {
    std::cin >> s[i];
    read(x);
    if (x) add(x, i);
    Fa[i] = x;
    t[i] = s[i];
  }
  std::sort(t + 1, t + n + 1);
  int len = std::unique(t + 1, t + n + 1) - t - 1;
  for (int i = 1; i <= n; ++i) {
    a[i] = std::lower_bound(t + 1, t + len + 1, s[i]) - t;
  }
  for (int i = 1; i <= n; ++i) {
    if (!Fa[i]) {
      _(i);
    }
  }
  int q;
  read(q);
  int y;
  for (int i = 1; i <= q; ++i) {
    read(x, y);
    v[x].emplace_back(std::make_pair(y + dep[x], i));
  }
  for (int i = 1; i <= n; ++i) {
    if (!Fa[i]) {
      dfs(i, 0);
    }
  }
  for (int i = 1; i <= q; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}