#include <bits/stdc++.h>
long long q_pow(long long x, long long n, long long mod) {
  long long ret = 1;
  while (n) {
    if (n & 1) ret = x * ret % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return ret;
}
long long __gcd(long long x, long long y) {
  if (!y) return x;
  return __gcd(y, x % y);
}
long long getbit(long long now) {
  int cnt = 0;
  while (now) {
    cnt++;
    now -= (now) & (-now);
  }
  return cnt;
}
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
using namespace std;
const long long maxn = 1e6 + 10;
const long long INF = 0x3f3f3f3f;
const long long IINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
int mod = 998244353;
vector<pair<int, int> > qry[maxn];
int ans[maxn];
vector<int> edge[maxn];
int dep[maxn], dp[maxn][21];
int son[maxn], sz[maxn];
int n;
int cnt[maxn];
void calc(int pos, int fa, int val) {
  cnt[dep[pos]] += val;
  for (auto to : edge[pos]) {
    if (to == fa) continue;
    calc(to, pos, val);
  }
}
void dfs1(int pos, int fa) {
  sz[pos] = 1;
  dp[pos][0] = fa;
  for (int i = 1; i <= 20; i++) dp[pos][i] = dp[dp[pos][i - 1]][i - 1];
  for (auto to : edge[pos]) {
    if (to == fa) continue;
    dep[to] = dep[pos] + 1;
    dfs1(to, pos);
    sz[pos] += sz[to];
    if (sz[to] > sz[son[pos]]) son[pos] = to;
  }
}
int find_k(int pos, int kth) {
  int delta = dep[pos] - kth;
  for (int i = 20; i >= 0; i--) {
    if (dep[dp[pos][i]] > delta) {
      pos = dp[pos][i];
    }
  }
  return dp[pos][0];
}
void dfs2(int pos, int fa, int flag) {
  for (auto to : edge[pos]) {
    if (to == son[pos]) continue;
    if (to == fa) continue;
    dfs2(to, pos, 0);
  }
  if (son[pos]) dfs2(son[pos], pos, 1);
  for (auto to : edge[pos]) {
    if (to == son[pos] or to == fa) continue;
    calc(to, pos, 1);
  }
  cnt[dep[pos]]++;
  for (auto to : qry[pos]) {
    ans[to.second] = cnt[dep[pos] + to.first];
  }
  if (!flag) calc(pos, fa, -1);
}
void solve() {
  cin >> n;
  int u;
  for (int i = 1; i <= n; i++) {
    cin >> u;
    edge[u].emplace_back(i);
  }
  dfs1(0, 0);
  int m;
  cin >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    int fa = find_k(u, v);
    if (fa != 0) qry[fa].emplace_back(make_pair(v, i));
  }
  dfs2(0, 0, 1);
  for (int i = 1; i <= m; i++) {
    cout << max(ans[i] - 1, 0) << " ";
  }
  cout << "\n";
}
signed main(int argc, char *argv[]) {
  if (argc == 2 && strcmp("-debug", argv[1]) == 0) {
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  }
  cout << fixed << setprecision(20);
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to 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>
long long q_pow(long long x, long long n, long long mod) {
  long long ret = 1;
  while (n) {
    if (n & 1) ret = x * ret % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return ret;
}
long long __gcd(long long x, long long y) {
  if (!y) return x;
  return __gcd(y, x % y);
}
long long getbit(long long now) {
  int cnt = 0;
  while (now) {
    cnt++;
    now -= (now) & (-now);
  }
  return cnt;
}
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
using namespace std;
const long long maxn = 1e6 + 10;
const long long INF = 0x3f3f3f3f;
const long long IINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
int mod = 998244353;
vector<pair<int, int> > qry[maxn];
int ans[maxn];
vector<int> edge[maxn];
int dep[maxn], dp[maxn][21];
int son[maxn], sz[maxn];
int n;
int cnt[maxn];
void calc(int pos, int fa, int val) {
  cnt[dep[pos]] += val;
  for (auto to : edge[pos]) {
    if (to == fa) continue;
    calc(to, pos, val);
  }
}
void dfs1(int pos, int fa) {
  sz[pos] = 1;
  dp[pos][0] = fa;
  for (int i = 1; i <= 20; i++) dp[pos][i] = dp[dp[pos][i - 1]][i - 1];
  for (auto to : edge[pos]) {
    if (to == fa) continue;
    dep[to] = dep[pos] + 1;
    dfs1(to, pos);
    sz[pos] += sz[to];
    if (sz[to] > sz[son[pos]]) son[pos] = to;
  }
}
int find_k(int pos, int kth) {
  int delta = dep[pos] - kth;
  for (int i = 20; i >= 0; i--) {
    if (dep[dp[pos][i]] > delta) {
      pos = dp[pos][i];
    }
  }
  return dp[pos][0];
}
void dfs2(int pos, int fa, int flag) {
  for (auto to : edge[pos]) {
    if (to == son[pos]) continue;
    if (to == fa) continue;
    dfs2(to, pos, 0);
  }
  if (son[pos]) dfs2(son[pos], pos, 1);
  for (auto to : edge[pos]) {
    if (to == son[pos] or to == fa) continue;
    calc(to, pos, 1);
  }
  cnt[dep[pos]]++;
  for (auto to : qry[pos]) {
    ans[to.second] = cnt[dep[pos] + to.first];
  }
  if (!flag) calc(pos, fa, -1);
}
void solve() {
  cin >> n;
  int u;
  for (int i = 1; i <= n; i++) {
    cin >> u;
    edge[u].emplace_back(i);
  }
  dfs1(0, 0);
  int m;
  cin >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    int fa = find_k(u, v);
    if (fa != 0) qry[fa].emplace_back(make_pair(v, i));
  }
  dfs2(0, 0, 1);
  for (int i = 1; i <= m; i++) {
    cout << max(ans[i] - 1, 0) << " ";
  }
  cout << "\n";
}
signed main(int argc, char *argv[]) {
  if (argc == 2 && strcmp("-debug", argv[1]) == 0) {
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  }
  cout << fixed << setprecision(20);
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}

```