#include <bits/stdc++.h>
using namespace std;
inline bool checkBit(long long n, int i) { return n & (1LL << i); }
inline long long setBit(long long n, int i) { return n | (1LL << i); }
inline long long resetBit(long long n, int i) { return n & (~(1LL << i)); }
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
inline double dist(double ix, double iy, double jx, double jy) {
  return sqrt(((ix - jx) * (ix - jx)) + ((iy - jy) * (iy - jy)));
}
int marked[1000000 / 64 + 2];
bool isPrime(int x) {
  return (x > 1) &&
         ((x == 2) ||
          ((x & 1) && (!((marked[x >> 6] & (1 << ((x & 63) >> 1)))))));
}
void seive(int n) {
  int i, j;
  for (i = 3; i * i <= n; i += 2) {
    if (!(marked[i >> 6] & (1 << ((i & 63) >> 1)))) {
      for (j = i * i; j <= n; j += i << 1) {
        marked[j >> 6] |= (1 << ((j & 63) >> 1));
      }
    }
  }
}
long long bigMod(long long a, long long b) {
  long long r = 1;
  while (b) {
    if (b & 1) (r *= a) %= 1000000007;
    b >>= 1;
    (a *= a) %= 1000000007;
  }
  return r;
}
long long add(long long a, long long b) {
  long long ret = a + b;
  if (ret >= 1000000007) ret -= 1000000007;
  return ret;
}
long long sub(long long a, long long b) {
  long long ret = a - b;
  if (ret < 0) ret += 1000000007;
  return ret;
}
int lv[500007], bigChild[500007], big[500007], cnt[500007], ans[500007],
    par[500007][25], n;
vector<int> edge[500007];
vector<pair<int, int> > q[500007];
int fsz(int i, int h) {
  ;
  lv[i] = h;
  int ret = 1, mx = 0;
  for (auto it : edge[i]) {
    int p = fsz(it, h + 1);
    par[it][0] = i;
    if (mx < p) {
      mx = p;
      bigChild[i] = it;
    }
    ret += p;
  }
  return ret;
}
void build_lca() {
  int i, j;
  for (j = 1; (1 << j) < n; j++)
    for (i = 1; i <= n; i++)
      if (par[i][j - 1] != -1) par[i][j] = par[par[i][j - 1]][j - 1];
}
int query(int i, int h) {
  int j = 20;
  while (h) {
    while (h < (1 << j)) j--;
    h -= (1 << j);
    i = par[i][j];
  }
  return i;
}
void add(int i, int x) {
  cnt[lv[i]] += x;
  for (auto it : edge[i])
    if (!big[it]) add(it, x);
}
void dfs(int i, bool keep) {
  ;
  for (auto it : edge[i])
    if (it != bigChild[i]) dfs(it, 0);
  if (bigChild[i]) dfs(bigChild[i], 1), big[bigChild[i]] = 1;
  add(i, 1);
  for (auto it : q[i]) {
    ans[it.second] = cnt[it.first] - 1;
  }
  if (bigChild[i]) big[bigChild[i]] = 0;
  if (keep == 0) add(i, -1);
}
int main() {
  int m, i, x, h, j;
  scanf("%d", &n);
  for (i = 0; i <= n; i++)
    for (j = 0; (1 << j) <= n; j++) par[i][j] = -1;
  for (i = 1; i <= n; i++) {
    scanf("%d", &x);
    edge[x].push_back(i);
  }
  fsz(0, 0);
  build_lca();
  scanf("%d", &m);
  for (i = 1; i <= m; i++) {
    scanf("%d %d", &x, &h);
    int p = query(x, h);
    ;
    if (p > 0)
      q[p].push_back({lv[p] + h, i});
    else
      ans[i] = 0;
  }
  dfs(0, 0);
  for (i = 1; i <= m; i++) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

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;
inline bool checkBit(long long n, int i) { return n & (1LL << i); }
inline long long setBit(long long n, int i) { return n | (1LL << i); }
inline long long resetBit(long long n, int i) { return n & (~(1LL << i)); }
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
inline double dist(double ix, double iy, double jx, double jy) {
  return sqrt(((ix - jx) * (ix - jx)) + ((iy - jy) * (iy - jy)));
}
int marked[1000000 / 64 + 2];
bool isPrime(int x) {
  return (x > 1) &&
         ((x == 2) ||
          ((x & 1) && (!((marked[x >> 6] & (1 << ((x & 63) >> 1)))))));
}
void seive(int n) {
  int i, j;
  for (i = 3; i * i <= n; i += 2) {
    if (!(marked[i >> 6] & (1 << ((i & 63) >> 1)))) {
      for (j = i * i; j <= n; j += i << 1) {
        marked[j >> 6] |= (1 << ((j & 63) >> 1));
      }
    }
  }
}
long long bigMod(long long a, long long b) {
  long long r = 1;
  while (b) {
    if (b & 1) (r *= a) %= 1000000007;
    b >>= 1;
    (a *= a) %= 1000000007;
  }
  return r;
}
long long add(long long a, long long b) {
  long long ret = a + b;
  if (ret >= 1000000007) ret -= 1000000007;
  return ret;
}
long long sub(long long a, long long b) {
  long long ret = a - b;
  if (ret < 0) ret += 1000000007;
  return ret;
}
int lv[500007], bigChild[500007], big[500007], cnt[500007], ans[500007],
    par[500007][25], n;
vector<int> edge[500007];
vector<pair<int, int> > q[500007];
int fsz(int i, int h) {
  ;
  lv[i] = h;
  int ret = 1, mx = 0;
  for (auto it : edge[i]) {
    int p = fsz(it, h + 1);
    par[it][0] = i;
    if (mx < p) {
      mx = p;
      bigChild[i] = it;
    }
    ret += p;
  }
  return ret;
}
void build_lca() {
  int i, j;
  for (j = 1; (1 << j) < n; j++)
    for (i = 1; i <= n; i++)
      if (par[i][j - 1] != -1) par[i][j] = par[par[i][j - 1]][j - 1];
}
int query(int i, int h) {
  int j = 20;
  while (h) {
    while (h < (1 << j)) j--;
    h -= (1 << j);
    i = par[i][j];
  }
  return i;
}
void add(int i, int x) {
  cnt[lv[i]] += x;
  for (auto it : edge[i])
    if (!big[it]) add(it, x);
}
void dfs(int i, bool keep) {
  ;
  for (auto it : edge[i])
    if (it != bigChild[i]) dfs(it, 0);
  if (bigChild[i]) dfs(bigChild[i], 1), big[bigChild[i]] = 1;
  add(i, 1);
  for (auto it : q[i]) {
    ans[it.second] = cnt[it.first] - 1;
  }
  if (bigChild[i]) big[bigChild[i]] = 0;
  if (keep == 0) add(i, -1);
}
int main() {
  int m, i, x, h, j;
  scanf("%d", &n);
  for (i = 0; i <= n; i++)
    for (j = 0; (1 << j) <= n; j++) par[i][j] = -1;
  for (i = 1; i <= n; i++) {
    scanf("%d", &x);
    edge[x].push_back(i);
  }
  fsz(0, 0);
  build_lca();
  scanf("%d", &m);
  for (i = 1; i <= m; i++) {
    scanf("%d %d", &x, &h);
    int p = query(x, h);
    ;
    if (p > 0)
      q[p].push_back({lv[p] + h, i});
    else
      ans[i] = 0;
  }
  dfs(0, 0);
  for (i = 1; i <= m; i++) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}

```