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 double pi = acos(0.0) * 2.0;
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <class T>
inline T max1(T a, T b) {
  return a > b ? a : b;
}
template <class T>
inline T min1(T a, T b) {
  return a < b ? a : b;
}
template <class T>
inline T gcd1(T a, T b) {
  if (a < b) swap(a, b);
  if (a % b == 0) return b;
  return gcd1(b, a % b);
}
template <class T>
inline T lb(T num) {
  return num & (-num);
}
template <class T>
inline int bitnum(T num) {
  int ans = 0;
  while (num) {
    num -= lb(num);
    ans++;
  }
  return ans;
}
long long pow(long long n, long long m, long long mod = 0) {
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
const int maxn = 310000;
template <class t>
struct tree_array {
  t num[maxn], n;
  void upd(int no, t add) {
    while (no <= n) {
      num[no] += add;
      no += lb(no);
    }
  }
  t que(int no) {
    t ans = 0;
    while (no) {
      ans += num[no];
      no -= lb(no);
    }
    return ans;
  }
};
tree_array<int> ta;
char name[maxn][100];
int son[25][maxn], fa[25][maxn];
vector<int> le[maxn], quen[maxn];
int nxten[maxn], qube[maxn];
pair<int, int> wh[maxn];
struct tree {
  int n;
  int root;
  int fa[maxn];
  int son_head[maxn], son_nxt[maxn];
  int size[maxn], hv[maxn], maxdeep[maxn];
  int level[maxn];
  inline tree() {
    n = 0;
    memset(fa, -1, sizeof(fa));
    memset(son_head, -1, sizeof(son_head));
    memset(hv, -1, sizeof(hv));
    memset(level, -1, sizeof(level));
    memset(size, 0, sizeof(size));
  }
  inline tree operator=(const tree *a) {
    tree a1;
    a1.n = a->n;
    a1.root = a->root;
    memcpy(a1.fa, a->fa, sizeof(a->fa));
    memcpy(a1.son_head, a->son_head, sizeof(a->son_head));
    memcpy(a1.son_nxt, a->son_nxt, sizeof(a->son_nxt));
    memcpy(a1.size, a->size, sizeof(a->size));
    memcpy(a1.hv, a->hv, sizeof(a->hv));
    memcpy(a1.level, a->level, sizeof(a->level));
    return a1;
  }
  void tree_init_edge() {
    for (int i = 0; i < n; i++) {
      if (fa[i] == -1) {
        root = i;
        continue;
      }
      son_nxt[i] = son_head[fa[i]];
      son_head[fa[i]] = i;
    }
  }
  void dfs(int no, int ranlevel = 0) {
    int rans = 0;
    level[no] = ranlevel;
    size[no] = 1;
    le[ranlevel].push_back(no);
    wh[no].first = ranlevel;
    wh[no].second = le[ranlevel].size() - 1;
    quen[ranlevel].push_back(-1);
    maxdeep[no] = ranlevel;
    for (int i = son_head[no]; i != -1; i = son_nxt[i]) {
      dfs(i, ranlevel + 1);
      if (size[i] > rans) {
        hv[no] = i;
        rans = size[i];
      }
      if (maxdeep[i] > maxdeep[no]) son[0][no] = i, maxdeep[no] = maxdeep[i];
      size[no] += size[i];
    }
  }
};
struct LCA {
  tree t;
  int a[maxn], st[maxn][25], d[30], la, wh[maxn], a1[maxn], st1[maxn][25];
  void dfs(int no) {
    a[la] = t.level[no];
    a1[la++] = no;
    for (int i = t.son_head[no]; i != -1; i = t.son_nxt[i]) {
      dfs(i);
      a[la] = t.level[no];
      a1[la++] = no;
    }
    wh[no] = la - 1;
  }
  void InitRMQ(const int &n) {
    int i, j;
    for (d[0] = 1, i = 1; i < 25; ++i) d[i] = 2 * d[i - 1];
    for (i = 0; i < n; ++i) {
      st[i][0] = a[i];
      st1[i][0] = a1[i];
    }
    int k = int(log(double(n)) / log(2)) + 1;
    for (j = 1; j < k; ++j)
      for (i = 0; i < n; ++i) {
        if (i + d[j - 1] - 1 < n) {
          st1[i][j] = t.level[st1[i][j - 1]] < t.level[st1[i + d[j - 1]][j - 1]]
                          ? st1[i][j - 1]
                          : st1[i + d[j - 1]][j - 1];
          st[i][j] = t.level[st1[i][j]];
        } else
          break;
      }
  }
  inline void buildLCA(tree *t1 = NULL) {
    if (t1 != NULL) {
      t = *t1;
      dfs(t.root);
      InitRMQ(la);
    }
  }
  inline int que_val(int x, int y) {
    if (x > y) swap(x, y);
    int k = int(log(double(y - x + 1)) / log(2.0));
    return min1(st[x][k], st[y - d[k] + 1][k]);
  }
  inline int que_no(int x, int y) {
    if (x > y) swap(x, y);
    int k = int(log(double(y - x + 1)) / log(2.0));
    return t.level[st1[x][k]] < t.level[st1[y - d[k] + 1][k]]
               ? st1[x][k]
               : st1[y - d[k] + 1][k];
  }
  inline int lcaque(int x, int y) { return que_val(wh[x], wh[y]); }
};
int n;
tree t;
LCA l;
int ans[maxn];
map<string, int> mp;
int rank1[maxn], lrank1 = 1;
int main() {
  memset(son, -1, sizeof(son));
  scanf("%d", &n);
  n++;
  t.n = n;
  t.root = 0;
  t.fa[0] = -1;
  for (int i = 1; i < n; i++) {
    scanf("%s%d", name[i], &t.fa[i]);
    string str;
    int l = strlen(name[i]);
    for (int i1 = 0; i1 < l; i1++) str += name[i][i1];
    if (mp[str] != 0)
      rank1[i] = mp[str];
    else {
      mp[str] = lrank1;
      rank1[i] = lrank1++;
    }
  }
  t.tree_init_edge();
  t.dfs(t.root);
  l.buildLCA(&t);
  for (int j = 0; j < n; j++) fa[0][j] = t.fa[j];
  for (int j = 1; j <= 20; j++)
    for (int i = 0; i < n; i++) {
      if (fa[j - 1][i] != -1)
        fa[j][i] = fa[j - 1][fa[j - 1][i]];
      else
        fa[j][i] = -1;
      if (son[j - 1][i] != -1)
        son[j][i] = son[j - 1][son[j - 1][i]];
      else
        son[j - 1][i] = -1;
    }
  int nq;
  scanf("%d", &nq);
  for (int i = 0; i < nq; i++) {
    int no, dai, randai, ranno;
    scanf("%d%d", &no, &dai);
    randai = dai;
    ranno = no;
    for (int i1 = 0, j = 1; dai && ranno != -1; j <<= 1, i1++) {
      if (dai & 1) ranno = son[i1][ranno];
      dai >>= 1;
    }
    if (ranno == -1) continue;
    int it = wh[ranno].second;
    int en = le[t.level[ranno]].size() - 1, be = it;
    while (be < en - 1) {
      int mid = (be + en) / 2;
      if (l.lcaque(le[t.level[ranno]][it], le[t.level[ranno]][mid]) <
          t.level[no])
        en = mid - 1;
      else
        be = mid;
    }
    if (!(l.lcaque(le[t.level[ranno]][it], le[t.level[ranno]][en]) <
          t.level[no]))
      be = en;
    int be1 = 0, en1 = it;
    while (be1 < en1 - 1) {
      int mid = (be1 + en1) / 2;
      if (l.lcaque(le[t.level[ranno]][mid], le[t.level[ranno]][it]) <
          t.level[no])
        be1 = mid + 1;
      else
        en1 = mid;
    }
    if (l.lcaque(le[t.level[ranno]][it], le[t.level[ranno]][be1]) < t.level[no])
      be1 = en1;
    nxten[i] = quen[t.level[ranno]][be];
    quen[t.level[ranno]][be] = i;
    qube[i] = be1;
  }
  pair<int, int> last[maxn];
  memset(last, -1, sizeof(last));
  ta.n = n + 10;
  int before = 0;
  for (int i = 0; i < maxn; i++) {
    for (int j = 0; j < (int)le[i].size(); j++) {
      if (last[rank1[le[i][j]]].first < i) {
        last[rank1[le[i][j]]].first = i;
        last[rank1[le[i][j]]].second = j;
      } else {
        last[rank1[le[i][j]]].first = i;
        ta.upd(last[rank1[le[i][j]]].second + 1 + before, 1);
        last[rank1[le[i][j]]].second = j;
      }
      for (int k = quen[i][j]; k != -1; k = nxten[k])
        ans[k] =
            j - qube[k] + 1 - ta.que(j + 1 + before) + ta.que(qube[k] + before);
    }
    before += le[i].size();
  }
  for (int i = 0; i < nq; i++) printf("%d\n", ans[i]);
  return 0;
}