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\).
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.
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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
2 3 1 5 6 4 2 10 7 7
5
10 1
5 7
10 6
1 1
10 8
|
3
0
1
1
0
|