#include <bits/stdc++.h>
using namespace std;
int n, m, heavy[100009], h[100009], ans[100009], up[100009][18], po[20],
    cnt[100009];
vector<int> v[100009];
vector<pair<int, int> > q[100009];
void add(int node, int val) {
  cnt[h[node]] += val;
  for (auto i : v[node]) add(i, val);
}
int dfs(int node, int p) {
  int sum = 1, mx = -1;
  h[node] = h[p] + 1;
  up[node][0] = p;
  for (int i = 1; i <= 16; i++) up[node][i] = up[up[node][i - 1]][i - 1];
  for (auto i : v[node]) {
    int x = dfs(i, node);
    sum += x;
    if (x > mx) mx = x, heavy[node] = i;
  }
  return sum;
}
void solve(int node, int keep) {
  for (auto i : v[node])
    if (i != heavy[node]) solve(i, 0);
  if (heavy[node]) solve(heavy[node], 1);
  for (auto i : v[node])
    if (i != heavy[node]) add(i, 1);
  cnt[h[node]]++;
  while (!q[node].empty()) {
    ans[q[node].back().second] = cnt[q[node].back().first] - 1;
    q[node].pop_back();
  }
  if (keep == 0) {
    for (auto i : v[node]) add(i, -1);
    cnt[h[node]]--;
  }
}
int kth_ancestor(int node, int k) {
  for (int i = 16; i >= 0; i--)
    if (po[i] <= k) node = up[node][i], k -= po[i];
  return node;
}
int main() {
  cin >> n;
  po[0] = 1;
  for (int i = 1; i <= 17; i++) po[i] = po[i - 1] * 2;
  vector<int> roots;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    if (x == 0)
      roots.push_back(i);
    else
      v[x].push_back(i);
  }
  for (auto i : roots) dfs(i, 0);
  cin >> m;
  for (int i = 1; i <= m; i++) {
    int vi, pi;
    cin >> vi >> pi;
    int x = kth_ancestor(vi, pi);
    if (x == 0) continue;
    q[x].push_back({pi + h[x], i});
  }
  for (auto i : roots) solve(i, 0);
  for (int i = 1; i <= m; i++) cout << ans[i] << " ";
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

Polycarpus got hold of a family relationship tree. The tree describes family relationships of n people, numbered 1 through n. Each person in the tree has no more than one parent.

Let's call person a a 1-ancestor of person b, if a is the parent of b.

Let's call person a a k-ancestor (k > 1) of person b, if person b has a 1-ancestor, and a is a (k - 1)-ancestor of b's 1-ancestor. 

Family relationships don't form cycles in the found tree. In other words, there is no person who is his own ancestor, directly or indirectly (that is, who is an x-ancestor for himself, for some x, x > 0).

Let's call two people x and y (x ≠ y) p-th cousins (p > 0), if there is person z, who is a p-ancestor of x and a p-ancestor of y.

Polycarpus wonders how many counsins and what kinds of them everybody has. He took a piece of paper and wrote m pairs of integers vi, pi. Help him to calculate the number of pi-th cousins that person vi has, for each pair vi, pi.

Input

The first input line contains a single integer n (1 ≤ n ≤ 105) — the number of people in the tree. The next line contains n space-separated integers r1, r2, ..., rn, where ri (1 ≤ ri ≤ n) is the number of person i's parent or 0, if person i has no parent. It is guaranteed that family relationships don't form cycles.

The third line contains a single number m (1 ≤ m ≤ 105) — the number of family relationship queries Polycarus has. Next m lines contain pairs of space-separated integers. The i-th line contains numbers vi, pi (1 ≤ vi, pi ≤ n).

Output

Print m space-separated integers — the answers to Polycarpus' queries. Print the answers to the queries in the order, in which the queries occur in the input.

Examples

Input

6
0 1 1 0 4 4
7
1 1
1 2
2 1
2 2
4 1
5 1
6 1


Output

0 0 1 0 0 1 1 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, heavy[100009], h[100009], ans[100009], up[100009][18], po[20],
    cnt[100009];
vector<int> v[100009];
vector<pair<int, int> > q[100009];
void add(int node, int val) {
  cnt[h[node]] += val;
  for (auto i : v[node]) add(i, val);
}
int dfs(int node, int p) {
  int sum = 1, mx = -1;
  h[node] = h[p] + 1;
  up[node][0] = p;
  for (int i = 1; i <= 16; i++) up[node][i] = up[up[node][i - 1]][i - 1];
  for (auto i : v[node]) {
    int x = dfs(i, node);
    sum += x;
    if (x > mx) mx = x, heavy[node] = i;
  }
  return sum;
}
void solve(int node, int keep) {
  for (auto i : v[node])
    if (i != heavy[node]) solve(i, 0);
  if (heavy[node]) solve(heavy[node], 1);
  for (auto i : v[node])
    if (i != heavy[node]) add(i, 1);
  cnt[h[node]]++;
  while (!q[node].empty()) {
    ans[q[node].back().second] = cnt[q[node].back().first] - 1;
    q[node].pop_back();
  }
  if (keep == 0) {
    for (auto i : v[node]) add(i, -1);
    cnt[h[node]]--;
  }
}
int kth_ancestor(int node, int k) {
  for (int i = 16; i >= 0; i--)
    if (po[i] <= k) node = up[node][i], k -= po[i];
  return node;
}
int main() {
  cin >> n;
  po[0] = 1;
  for (int i = 1; i <= 17; i++) po[i] = po[i - 1] * 2;
  vector<int> roots;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    if (x == 0)
      roots.push_back(i);
    else
      v[x].push_back(i);
  }
  for (auto i : roots) dfs(i, 0);
  cin >> m;
  for (int i = 1; i <= m; i++) {
    int vi, pi;
    cin >> vi >> pi;
    int x = kth_ancestor(vi, pi);
    if (x == 0) continue;
    q[x].push_back({pi + h[x], i});
  }
  for (auto i : roots) solve(i, 0);
  for (int i = 1; i <= m; i++) cout << ans[i] << " ";
  return 0;
}

```