题目描述

给定一个序列，一次转换是将一个数变成这个数在这个序列中出现的次数。

序列 $\{2,1,1,4,3,1,2\}$ 中，$2$ 出现 $2$ 次，$1$ 出现 $3$ 次，$3$ 和 $4$ 出现 $1$ 次，那么这个序列进行一次转换之后就变成了 $\{2,3,3,1,1,3,2\}$，同理，进行两次转换后是 $\{2,3,3,2,2,3,2\}$，进行三次转换后是 $\{4,3,3,4,4,3,4\}$。

有 $q$ 次询问，每次询问第 $x$ 个位置的元素经过 $k$ 次转换之后是什么。

输入格式

第一行输入一个正整数 $t$ 表示数据组数。

对于每一组数据：

• 第一行输入一个正整数 $n$ 表示序列长度。
• 第二行输入 $n$ 个正整数 $a_i$ 表示初始序列。
• 第三行输入一个正整数 $q$ 表示询问次数。

输出格式

对于每一个询问输出一行一个正整数表示答案。

说明/提示

$1\le t\le1000,1\le\sum n\le2000,1\le a_i,x\le n,1\le\sum q\le10^5，0\le k\le10^9$。

样例

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