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>
int oo[1 + 200000 - 1], oj[1 + 200000 - 1];
int link(int o, int j) {
  static int _ = 1;
  oo[_] = o, oj[_] = j;
  return _++;
}
int ae[200000], ca[200000], cb[200000], dd[200000], ta[200000], tb[200000], n,
    n_;
void dfs(int i, int d) {
  static int time;
  int o;
  ta[i] = time++;
  for (o = ae[i]; o; o = oo[o]) {
    int j = oj[o];
    dfs(j, d + 1);
  }
  tb[i] = time;
}
int compare1(const void *a, const void *b) {
  int i = *(int *)a;
  int j = *(int *)b;
  return dd[i] != dd[j] ? dd[i] - dd[j] : ta[i] - ta[j];
}
int compare2(const void *a, const void *b) {
  int i = *(int *)a;
  int j = *(int *)b;
  return ca[i] != ca[j] ? ca[i] - ca[j]
                        : (cb[i] != cb[j] ? cb[i] - cb[j] : dd[i] - dd[j]);
}
int ii[200000], jj[200000];
int search1(long long d, int a) {
  int lower = -1, upper = n;
  while (upper - lower > 1) {
    int h = (lower + upper) / 2, i = ii[h];
    if (dd[i] < d || dd[i] == d && ta[i] <= a)
      lower = h;
    else
      upper = h;
  }
  return lower + 1;
}
int search2(int a, int b, long long d) {
  int lower = -1, upper = n_;
  while (upper - lower > 1) {
    int h = (lower + upper) / 2, j = jj[h];
    if (ca[j] < a || ca[j] == a && (cb[j] < b || cb[j] == b && dd[j] <= d))
      lower = h;
    else
      upper = h;
  }
  return lower + 1;
}
int main() {
  static int aa[200000], ll[200000 + 1];
  static char cycle[200000];
  int m, q, i, d;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &aa[i]), aa[i]--;
  scanf("%d", &q);
  m = 0;
  for (i = 0; i < n; i++) {
    int j, a, b, l;
    if (ca[i]) continue;
    j = i, d = 0;
    while (!ca[j]) {
      ca[j] = -1;
      j = aa[j], d++;
    }
    if (ca[j] == -1) {
      a = ++m;
      l = 0;
      while (ca[j] == -1) {
        ca[j] = -2;
        l++;
        cycle[j] = 1;
        j = aa[j];
      }
      ll[a] = l, b = 0;
      d -= l;
    } else {
      a = ca[j], l = ll[a], b = (cb[j] - d) % l;
      if (b < 0) b += l;
      d += dd[j];
    }
    j = i;
    while (ca[j] < 0) {
      ca[j] = a, cb[j] = b++ % l, dd[j] = cycle[j] ? 0 : d--;
      j = aa[j];
    }
  }
  for (i = 0; i < n; i++)
    if (!cycle[i]) ae[aa[i]] = link(ae[aa[i]], i);
  for (i = 0; i < n; i++)
    if (cycle[i]) dfs(i, 0);
  for (i = 0; i < n; i++) ii[i] = i;
  qsort(ii, n, sizeof *ii, compare1);
  for (i = 0; i < n; i++)
    if (!cycle[i]) jj[n_++] = i;
  qsort(jj, n_, sizeof *jj, compare2);
  while (q--) {
    long long k;
    scanf("%lld%d", &k, &i), i--;
    if (!cycle[i])
      printf("%d\n",
             search1(dd[i] + k, tb[i] - 1) - search1(dd[i] + k, ta[i] - 1));
    else {
      int a = ca[i], b = (cb[i] - k) % ll[a];
      if (b < 0) b += ll[a];
      printf("%d\n", 1 + search2(a, b, dd[i] + k) - search2(a, b, -1));
    }
  }
  return 0;
}
