CF1602B.Divine Array

Black is gifted with a Divine array $a$ consisting of $n$ ($1 \le n \le 2000$) integers. Each position in $a$ has an initial value. After shouting a curse over the array, it becomes angry and starts an unstoppable transformation.

The transformation consists of infinite steps. Array $a$ changes at the $i$-th step in the following way: for every position $j$, $a_j$ becomes equal to the number of occurrences of $a_j$ in $a$ before starting this step.

Here is an example to help you understand the process better:

Initial array:

$2$ $1$ $1$ $4$ $3$ $1$ $2$

After the $1$-st step:

$2$ $3$ $3$ $1$ $1$ $3$ $2$

After the $2$-nd step:

$2$ $3$ $3$ $2$ $2$ $3$ $2$

After the $3$-rd step:

$4$ $3$ $3$ $4$ $4$ $3$ $4$

...

...

In the initial array, we had two $2$-s, three $1$-s, only one $4$ and only one $3$, so after the first step, each element became equal to the number of its occurrences in the initial array: all twos changed to $2$, all ones changed to $3$, four changed to $1$ and three changed to $1$.

The transformation steps continue forever.

You have to process $q$ queries: in each query, Black is curious to know the value of $a_x$ after the $k$-th step of transformation.

Black 拥有一个神圣数组 $a$，该数组由 $n$（$1 \le n \le 2000$）个整数组成。数组 $a$ 的每个位置都有一个初始值。在对数组施放一道咒语后，它变得愤怒，并开始一场不可阻挡的变换。

该变换由无限多步组成。在第 $i$ 步中，数组 $a$ 按如下方式变化：对每个位置 $j$，$a_j$ 的新值等于在本步开始前整个数组 $a$ 中值为 $a_j$ 的元素出现次数。

以下示例有助于你更好地理解该过程：

初始数组：

$2$ $1$ $1$ $4$ $3$ $1$ $2$

第 $1$ 步后：

$2$ $3$ $3$ $1$ $1$ $3$ $2$

第 $2$ 步后：

$2$ $3$ $3$ $2$ $2$ $3$ $2$

第 $3$ 步后：

$4$ $3$ $3$ $4$ $4$ $3$ $4$

...

...

在初始数组中，数字 $2$ 出现了两次，数字 $1$ 出现了三次，数字 $4$ 和 $3$ 各出现一次。因此，在第 $1$ 步中，每个元素均被替换为其在初始数组中的出现频次：所有 $2$ 变为 $2$，所有 $1$ 变为 $3$，$4$ 变为 $1$，$3$ 也变为 $1$。

该变换将永远持续下去。

你需要处理 $q$ 个查询：对每个查询，Black 希望知道经过变换的第 $k$ 步后，位置 $x$ 上的元素 $a_x$ 的值。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2000$）—— 数组 $a$ 的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）—— 数组 $a$ 的初始值。

每个测试用例的第三行包含一个整数 $q$（$1 \le q \le 100\,000$）—— 查询的数量。

接下来的 $q$ 行描述查询信息，每行一个查询。第 $i$ 行包含两个整数 $x_i$ 和 $k_i$（$1 \le x_i \le n$；$0 \le k_i \le 10^9$），表示 Black 想知道经过 $k_i$ 次变换后 $a_{x_i}$ 的值。其中 $k_i = 0$ 表示 Black 关心的是数组的初始值。

保证所有测试用例的 $n$ 之和不超过 $2000$，且所有测试用例的 $q$ 之和不超过 $100\,000$。

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.

对于每个测试用例，输出 $q$ 个答案。其中第 $i$ 个答案应为经过第 $k_i$ 步变换后 $a_{x_i}$ 的值。可以证明，每个查询的答案是唯一的。

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,

Initial array:

$1$ $1$

After the $1$-st step:

$2$ $2$

After the $2$-nd step:

$2$ $2$

...

...

It can be seen that:

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

第一个测试用例已在题目描述中给出。可以观察到：

1. $k_1 = 0$（初始数组）：$a_3 = 1$；
2. $k_2 = 1$（第 $1$ 步之后）：$a_1 = 2$；
3. $k_3 = 2$（第 $2$ 步之后）：$a_2 = 3$；
4. $k_4 = 1$（第 $1$ 步之后）：$a_6 = 3$。

对于第二个测试用例，

初始数组：

$1$ $1$

第 $1$ 步之后：

$2$ $2$

第 $2$ 步之后：

$2$ $2$

...

...

可以观察到：

1. $k_1 = 0$（初始数组）：$a_1 = 1$；
2. $k_2 = 1000000000$：$a_2 = 2$；