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;
long long read() {
  long long x = 0, F = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') F = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + c - '0';
    c = getchar();
  }
  return x * F;
}
int n, m, fa[200000 + 5], du[200000 + 5], ans[200000 + 5];
vector<pair<long long, int> > qry[200000 + 5];
vector<int> cnt[200000 + 5];
queue<int> Q;
void merge(vector<int> &A, vector<int> &B) {
  if (A.size() < B.size()) swap(A, B);
  for (int i = 1; i <= B.size(); i++) A[A.size() - i] += B[B.size() - i];
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) {
    fa[i] = read();
    du[fa[i]]++;
  }
  m = read();
  for (int i = 1; i <= m; i++) {
    long long x = read();
    int y = read();
    qry[y].push_back(pair<long long, int>(x, i));
  }
  for (int i = 1; i <= n; i++) {
    if (!du[i]) Q.push(i);
    cnt[i].push_back(1);
  }
  while (!Q.empty()) {
    int x = Q.front();
    Q.pop();
    for (int i = 0; i < qry[x].size(); i++) {
      long long t = qry[x][i].first;
      int pos = qry[x][i].second;
      if (t >= cnt[x].size())
        ans[pos] = 0;
      else
        ans[pos] = cnt[x][cnt[x].size() - t - 1];
    }
    cnt[x].push_back(0);
    merge(cnt[fa[x]], cnt[x]);
    du[fa[x]]--;
    if (!du[fa[x]]) Q.push(fa[x]);
  }
  for (int j = 1; j <= n; j++)
    if (du[j]) {
      int p = j, siz = 0;
      vector<int> cyc, tmp;
      do {
        du[p] = 0;
        tmp = cnt[p];
        merge(cyc, tmp);
        siz++;
        cyc.push_back(0);
        p = fa[p];
      } while (p != j);
      for (int i = 1; i + siz <= cyc.size(); i++)
        cyc[cyc.size() - i - siz] += cyc[cyc.size() - i];
      do {
        merge(cyc, cnt[p]);
        for (int i = 0; i < qry[p].size(); i++) {
          long long t = cyc.size() - qry[p][i].first - 1;
          int pos = qry[p][i].second;
          if (t < 0) t = (t % siz + siz) % siz;
          ans[pos] = cyc[t];
        }
        p = fa[p];
        cyc.push_back(0);
      } while (p != j);
    }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}
