Description

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 2000$) — the size of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the initial values of array $a$.

The third line of each test case contains a single integer $q$ ($1 \le q \le 100\,000$) — the number of queries.

Next $q$ lines contain the information about queries — one query per line. The $i$-th line contains two integers $x_i$ and $k_i$ ($1 \le x_i \le n$; $0 \le k_i \le 10^9$), meaning that Black is asking for the value of $a_{x_i}$ after the $k_i$-th step of transformation. $k_i = 0$ means that Black is interested in values of the initial array.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2000$ and the sum of $q$ over all test cases doesn't exceed $100\,000$.

Output

For each test case, print $q$ answers. The $i$-th of them should be the value of $a_{x_i}$ after the $k_i$-th step of transformation. It can be shown that the answer to each query is unique.

2
7
2 1 1 4 3 1 2
4
3 0
1 1
2 2
6 1
2
1 1
2
1 0
2 1000000000

1
2
3
3
1
2

Note

The first test case was described ih the statement. It can be seen that:

1. $k_1 = 0$ (initial array): $a_3 = 1$;
2. $k_2 = 1$ (after the $1$-st step): $a_1 = 2$;
3. $k_3 = 2$ (after the $2$-nd step): $a_2 = 3$;
4. $k_4 = 1$ (after the $1$-st step): $a_6 = 3$.

For the second test case,

It can be seen that:

1. $k_1 = 0$ (initial array): $a_1 = 1$;
2. $k_2 = 1000000000$: $a_2 = 2$;