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;
inline char gc() {
  static const long long L = 233333;
  static char sxd[L], *sss = sxd, *ttt = sxd;
  if (sss == ttt) {
    ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
    if (sss == ttt) {
      return EOF;
    }
  }
  return *sss++;
}
inline char readalpha() {
  char c = gc();
  for (; !isalpha(c); c = gc())
    ;
  return c;
}
inline char readchar() {
  char c = gc();
  for (; c == ' '; c = gc())
    ;
  return c;
}
template <class T>
inline bool read(T &x) {
  bool flg = false;
  char c = gc();
  x = 0;
  for (; !isdigit(c); c = gc()) {
    if (c == '-') {
      flg = true;
    } else if (c == EOF) {
      return false;
    }
  }
  for (; isdigit(c); c = gc()) {
    x = (x << 1) + (x << 3) + (c ^ 48);
  }
  if (flg) {
    x = -x;
  }
  return true;
}
template <class T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x < 10) {
    putchar(x | 48);
    return;
  }
  write(x / 10);
  putchar((x % 10) | 48);
}
const int mod = 1000000009;
const int sqrt5 = 383008016;
const int inv2 = 500000005;
const int isqrt5 = 276601605;
const int phi1 = 691504013;
const int phi2 = 308495997;
inline int ksm(int a, int b) {
  long long ans = 1;
  for (; b; b >>= 1, a = (long long)a * a % mod) {
    if (b & 1) {
      ans = (long long)ans * a % mod;
    }
  }
  return ans;
}
inline void merge(vector<int> &a, vector<int> &b) {
  if (a.size() < b.size()) {
    swap(a, b);
  }
  for (unsigned i = 1; i <= b.size(); ++i) {
    a[a.size() - i] += b[b.size() - i];
  }
}
const int maxn = 200005;
int n, q;
int fa[maxn];
int rd[maxn];
int ans[maxn];
vector<pair<long long, int> > que[maxn];
vector<int> dp[maxn];
int main() {
  read(n);
  for (int i = 1; i <= n; ++i) {
    read(fa[i]);
    rd[fa[i]]++;
  }
  read(q);
  for (int i = 1; i <= q; ++i) {
    long long x;
    int y;
    read(x), read(y);
    que[y].emplace_back(x, i);
  }
  queue<int> leaves;
  for (int i = 1; i <= n; ++i) {
    if (!rd[i]) {
      leaves.push(i);
    }
    dp[i].push_back(1);
  }
  while (!leaves.empty()) {
    int now = leaves.front();
    leaves.pop();
    for (auto qq : que[now]) {
      if (qq.first >= (int)dp[now].size()) {
        ans[qq.second] = 0;
      } else {
        ans[qq.second] = dp[now][dp[now].size() - qq.first - 1];
      }
    }
    dp[now].push_back(0);
    merge(dp[fa[now]], dp[now]);
    rd[fa[now]]--;
    if (!rd[fa[now]]) {
      leaves.push(fa[now]);
    }
  }
  for (int now = 1; now <= n; ++now) {
    if (rd[now]) {
      int noww = now;
      int len = 0;
      vector<int> yuan;
      do {
        auto bak = dp[noww];
        merge(yuan, bak);
        len++;
        yuan.push_back(0);
        noww = fa[noww];
        rd[noww] = 0;
      } while (noww != now);
      for (unsigned i = 1; i + len <= yuan.size(); ++i) {
        yuan[yuan.size() - i - len] += yuan[yuan.size() - i];
      }
      do {
        merge(yuan, dp[noww]);
        for (auto qq : que[noww]) {
          qq.first = (long long)yuan.size() - qq.first - 1;
          if (qq.first < 0) {
            qq.first %= len;
            if (qq.first) {
              qq.first += len;
            }
          }
          ans[qq.second] = yuan[qq.first];
        }
        noww = fa[noww];
        yuan.push_back(0);
      } while (noww != now);
    }
  }
  for (int i = 1; i <= q; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
