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;
inline void pisz(int n) { printf("%d\n", n); }
template <typename T, typename TT>
ostream& operator<<(ostream& s, pair<T, TT> t) {
  return s << "(" << t.first << "," << t.second << ")";
}
template <typename T>
ostream& operator<<(ostream& s, vector<T> t) {
  for (int(i) = 0; (i) < (((int)((t).size()))); ++(i)) s << t[i] << " ";
  return s;
}
int parent[100006], name[100006], newnum[100006], maxnum[100006], depth[100006];
char s[30];
vector<int> children[100006];
int ans[100006];
int nextnum = 0;
void dfs(int v, int d) {
  depth[v] = d;
  newnum[v] = nextnum++;
  maxnum[v] = newnum[v];
  for (typeof(children[v].begin()) x = children[v].begin();
       x != children[v].end(); x++) {
    dfs(*x, 1 + d);
    (maxnum[v]) = max((maxnum[v]), (maxnum[*x]));
    ;
  }
}
vector<pair<pair<int, int>, int> > todo[100006];
namespace Fenwick {
int a[100006];
vector<int> nonzero;
void add(int n, int x) {
  for (; n < 100006; n |= n + 1) {
    a[n] += x;
    nonzero.push_back(n);
  }
}
int sum(int n) {
  int s = 0;
  while (n >= 0) {
    s += a[n];
    n = (n & (n + 1)) - 1;
  }
  return s;
}
void clear() {
  for (typeof(nonzero.begin()) x = nonzero.begin(); x != nonzero.end(); x++)
    a[*x] = 0;
  nonzero.clear();
}
int sumbetween(int x, int y) {
  int res = sum(y);
  if (x > 0) res -= sum(x - 1);
  return res;
}
};  // namespace Fenwick
vector<pair<int, int> > onDepth[100006];
int main() {
  int(n);
  scanf("%d", &(n));
  parent[0] = -1;
  name[0] = 0;
  map<string, int> mapa;
  int q = 1;
  for (int(i) = 1; (i) <= (n); ++(i)) {
    scanf("%s %d", s, parent + i);
    if (!((mapa).find((s)) != (mapa).end())) mapa[s] = q++;
    name[i] = mapa[s];
  }
  for (int(i) = 1; (i) <= (n); ++(i)) children[parent[i]].push_back(i);
  dfs(0, 0);
  int(queries);
  scanf("%d", &(queries));
  for (int(q) = 0; (q) < (queries); ++(q)) {
    int(v), (lev);
    scanf("%d %d", &(v), &(lev));
    ans[q] = 0;
    if (depth[v] + lev <= 100000)
      todo[depth[v] + lev].push_back(
          make_pair(make_pair(newnum[v], maxnum[v]), q));
  }
  for (int(i) = 1; (i) <= (n); ++(i)) {
    onDepth[depth[i]].push_back(make_pair(newnum[i], name[i]));
  }
  for (int(lv) = 1; (lv) <= (100000); ++(lv)) {
    map<int, int> lastOccurOnThisLevel;
    sort(onDepth[lv].begin(), onDepth[lv].end());
    vector<pair<int, int> > pts;
    for (typeof(onDepth[lv].begin()) it = onDepth[lv].begin();
         it != onDepth[lv].end(); it++) {
      int v = it->first, nm = it->second;
      int prev = lastOccurOnThisLevel[nm] - 1;
      lastOccurOnThisLevel[nm] = v + 1;
      pts.push_back(make_pair(prev, v));
    }
    sort(pts.begin(), pts.end());
    int nowToAdd = 0;
    Fenwick::clear();
    sort(todo[lv].begin(), todo[lv].end());
    for (typeof(todo[lv].begin()) qr = todo[lv].begin(); qr != todo[lv].end();
         qr++) {
      int le = qr->first.first, ri = qr->first.second, queryNumber = qr->second;
      while (nowToAdd < ((int)((pts).size())) && pts[nowToAdd].first < le) {
        Fenwick::add(pts[nowToAdd].second, 1);
        nowToAdd++;
      }
      ans[queryNumber] = Fenwick::sumbetween(le, ri);
    }
  }
  for (int(q) = 0; (q) < (queries); ++(q)) pisz(ans[q]);
}