We are definitely not going to bother you with another generic story when Alice finds about an array or when Alice and Bob play some stupid game. This time you'll get a simple, plain text.

First, let us define several things. We define function F on the array A such that F(i, 1) = A[i] and F(i, m) = A[F(i, m - 1)] for m > 1. In other words, value F(i, m) represents composition A[...A[i]] applied m times.

You are given an array of length N with non-negative integers. You are expected to give an answer on Q queries. Each query consists of two numbers – m and y. For each query determine how many x exist such that F(x,m) = y.

Input

The first line contains one integer N (1 ≤ N ≤ 2 ⋅ 10^5) – the size of the array A. The next line contains N non-negative integers – the array A itself (1 ≤ A_i ≤ N). The next line contains one integer Q (1 ≤ Q ≤ 10^5) – the number of queries. Each of the next Q lines contain two integers m and y (1 ≤ m ≤ 10^{18}, 1≤ y ≤ N).

Output

Output exactly Q lines with a single integer in each that represent the solution. Output the solutions in the order the queries were asked in.

Example

Input


10
2 3 1 5 6 4 2 10 7 7
5
10 1
5 7
10 6
1 1
10 8


Output


3
0
1
1
0

Note

For the first query we can notice that F(3, 10) = 1,\ F(9, 10) = 1 and F(10, 10) = 1.

For the second query no x satisfies condition F(x, 5) = 7.

For the third query F(5, 10) = 6 holds.

For the fourth query F(3, 1) = 1.

For the fifth query no x satisfies condition F(x, 10) = 8.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> f[200001];
int l[200001], cc;
bool vis[200001];
int g[200001], h[200001], c[200001], p[200001];
bool dfs_cyc(int u, int d) {
  if (vis[u]) {
    if (!c[u]) {
      c[u] = ++cc;
      l[c[u]] = d - p[u];
      h[u] = 0;
      p[u] = 0;
      return true;
    } else
      return false;
  } else {
    p[u] = d;
    vis[u] = 1;
    bool flg = dfs_cyc(g[u], d + 1);
    c[u] = c[g[u]];
    p[u] = p[g[u]] ? p[g[u]] - 1 : l[c[u]] - 1;
    if (!flg)
      h[u] = h[g[u]] + 1;
    else
      h[u] = 0;
    if (!h[u])
      return p[u];
    else
      return false;
  }
}
int ls[200001 * 20], rs[200001 * 20], st[200001 * 20], rt[200001], nc;
int cp(int q) {
  int p = ++nc;
  ls[p] = ls[q];
  rs[p] = rs[q];
  st[p] = st[q];
  return p;
}
void modify(int x, int v, int p, int lb, int rb) {
  st[p] += v;
  if (lb + 1 == rb)
    return;
  else {
    int mid = (lb + rb) >> 1;
    if (x < mid)
      modify(x, v, ls[p] = cp(ls[p]), lb, mid);
    else
      modify(x, v, rs[p] = cp(rs[p]), mid, rb);
  }
}
int query(int x, int lp, int rp, int lb, int rb) {
  if (x >= rb) return 0;
  if (lb + 1 == rb)
    return st[rp] - st[lp];
  else {
    int mid = (lb + rb) >> 1;
    if (x < mid)
      return query(x, ls[lp], ls[rp], lb, mid);
    else
      return query(x, rs[lp], rs[rp], mid, rb);
  }
}
vector<int> gt[200001];
int dlb[200001], drb[200001], dfc;
void dfs_dfn(int u) {
  dlb[u] = ++dfc;
  modify(h[u], 1, rt[dfc] = cp(rt[dfc - 1]), 0, n);
  for (int v : gt[u]) dfs_dfn(v);
  drb[u] = dfc;
}
int main(void) {
  scanf("%d", &n);
  for (int u = 1; u <= n; ++u) scanf("%d", g + u);
  for (int u = 1; u <= n; ++u) dfs_cyc(u, 1);
  for (int w = 1; w <= cc; ++w) f[w].resize(l[w]);
  for (int u = 1; u <= n; ++u) {
    f[c[u]][p[u]].push_back(h[u]);
    if (h[u]) gt[g[u]].push_back(u);
  }
  for (int w = 1; w <= cc; ++w)
    for (int p = 0; p != l[w]; ++p) sort(f[w][p].begin(), f[w][p].end());
  for (int u = 1; u <= n; ++u)
    if (!h[u]) dfs_dfn(u);
  int q;
  scanf("%d", &q);
  while (q--) {
    long long m;
    int u;
    scanf("%lld%d", &m, &u);
    int w = c[u], ans;
    if (!h[u]) {
      int t = (p[u] - (m % l[w]) + l[w]) % l[w];
      int d = m % l[w];
      ans = upper_bound(f[w][t].begin(), f[w][t].end(), m) - f[w][t].begin();
    } else {
      ans = query(m + h[u], rt[dlb[u] - 1], rt[drb[u]], 0, n);
    }
    printf("%d\n", ans);
  }
  return 0;
}
