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$.

The first line contains one integer $N$ $(1 \leq N \leq 2 \cdot 10^5)$ – the size of the array $A$. The next line contains $N$ non-negative integers – the array $A$ itself $(1 \leq A_i \leq N)$. The next line contains one integer $Q$ $(1 \leq Q \leq 10^5)$ – the number of queries. Each of the next $Q$ lines contain two integers $m$ and $y$ $(1 \leq m \leq 10^{18}, 1\leq y \leq N)$.

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.