bee 3029 - Function Composition

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⁵ ) – the size of the array A. The next line contains N non-negative integers – the array A itself (1 ≤ Ai ≤ N ). The next line contains one integer Q (1 ≤ Q ≤ 10⁵ ) – the number of queries. Each of the next Q lines contain two integers m and y (1 ≤ m ≤ 10¹⁸ , 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.

Input Sample	Output Sample
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