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;
const int N = 2e5 + 234;
vector<pair<int, int> > arpa[N], pasha[N];
int mark[N], cmp[N], plCycl[N], Next[N];
int st[N], en[N], hei[N], now;
vector<int> Prev[N], cycles[N], height[N];
int goPrev(int x, long long n) {
  int cLen = ((int)cycles[cmp[x]].size());
  n = cLen - (n % cLen);
  return cycles[cmp[x]][(plCycl[x] + n) % cLen];
}
int goNext(int x, int cnt, int first) {
  mark[x] = first;
  if (mark[Next[x]] != first and mark[Next[x]] != -1) return 0;
  if (mark[Next[x]] == first) {
    int now = x;
    while (true) {
      plCycl[now] = ((int)cycles[cnt].size());
      cycles[cnt].push_back(now);
      cmp[now] = cnt;
      if (Next[now] == x) break;
      now = Next[now];
    }
    return 1;
  }
  return goNext(Next[x], cnt, first);
}
void dfs(int x, int root, int h = 0) {
  st[x] = now++;
  height[h].push_back(st[x]);
  hei[x] = h;
  arpa[goPrev(root, h)].push_back({h, 1});
  for (auto u : Prev[x])
    if (cmp[u] == -1) dfs(u, root, h + 1);
  en[x] = now;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  memset(mark, -1, sizeof mark);
  memset(cmp, -1, sizeof cmp);
  int n, q;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int t;
    cin >> t;
    t--;
    Next[i] = t;
    Prev[t].push_back(i);
  }
  int cnt = 0;
  for (int i = 0; i < n; i++)
    if (mark[i] == -1) cnt += goNext(i, cnt, i);
  for (int i = 0; i < n; i++) {
    if (cmp[i] != -1) dfs(i, i);
  }
  for (int i = 0; i < n; i++)
    if (cmp[i] != -1) {
      sort(arpa[i].begin(), arpa[i].end());
      for (int j = 0; j < ((int)arpa[i].size()); j++)
        if (j < ((int)arpa[i].size()) - 1 and
            arpa[i][j].first == arpa[i][j + 1].first)
          arpa[i][j + 1].second += arpa[i][j].second;
        else
          pasha[i].push_back(
              {arpa[i][j].first,
               arpa[i][j].second +
                   (((int)pasha[i].size()) ? pasha[i].back().second : 0)});
    }
  cin >> q;
  while (q--) {
    long long m, x;
    cin >> m >> x;
    x--;
    if (cmp[x] != -1) {
      int root = goPrev(x, m);
      auto it = upper_bound(pasha[root].begin(), pasha[root].end(),
                            pair<int, int>(min<long long>(m, N), N));
      it--;
      cout << (*it).second << '\n';
    } else {
      if (m + hei[x] >= N)
        cout << 0 << '\n';
      else
        cout << lower_bound(height[hei[x] + m].begin(),
                            height[hei[x] + m].end(), en[x]) -
                    lower_bound(height[hei[x] + m].begin(),
                                height[hei[x] + m].end(), st[x])
             << '\n';
    }
  }
  return 0;
}
