Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

H. Function Composition

time limit per test

0.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputWe 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 \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

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/19/2020 05:27:43 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|