CF 751 --B. Divine Array

Black is gifted with a Divine array a consisting of n (1≤n≤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, aj becomes equal to the number of occurrences of aj 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 ax after the k-th step of transformation.

Input

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

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

The second line of each test case contains n integers a1,a2,…,an, (1≤ai≤n) — the initial values of array a.

The third line of each test case contains a single integer q (1≤q≤100000) — the number of queries.

Next q lines contain the information about queries — one query per line. The i-th line contains two integers xi and ki (1≤xi≤n; 0≤ki≤10^9), meaning that Black is asking for the value of axi after the ki-th step of transformation. ki=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 100000.

Output

For each test case, print q answers. The i-th of them should be the value of axi after the ki-th step of transformation. It can be shown that the answer to each query is unique.

input

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

output

1
2
3
3
1
2

题意：给定一个序列，一次转化会把a[ i ]变成a[ i ]在此时序列中出现的次数，然后给q个询问，问k次转化后，a[x]的值。

解析：因为询问个数很多，如果我们每次询问都从头开始转化，那么就会超时了，因此我们可以先把每个询问读进来，离线操作，k从小到大开始记录答案。

注意：可以发现一个序列经过若干次转化后，当每个a[ i ]等于出现次数时，那么序列就不会再发生变化。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N];
struct s
{int x,k,ans,id;
}tr[N];
bool cmp1(s a,s b)//根据k从小到大排序
{return a.k<b.k;
}
bool cmp2(s a,s b)//为了根据输入顺序输出答案
{return a.id<b.id;
}
void solve()
{int n,q;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);scanf("%d",&q);for(int i=1;i<=q;i++) scanf("%d%d",&tr[i].x,&tr[i].k),tr[i].id=i;sort(tr+1,tr+q+1,cmp1);//根据k排序int cnt=0,f=0;//cnt和f分别表示当前第几轮转化和是否是达到不变状态for(int i=1;i<=q;i++){int x=tr[i].x,k=tr[i].k;while(k>cnt&&!f){vector<int> mp(n+5);//记录每个数出现的个数int ok=1;//判断是否每个数都等于当前出现次数for(int j=1;j<=n;j++) mp[a[j]]++;//对应出现次数+1for(int j=1;j<=n;j++){if(a[j]!=mp[a[j]]){ok=0;//没有达到不变状态break;}}if(ok) f=1;if(f) break;for(int j=1;j<=n;j++) a[j]=mp[a[j]];//更新序列cnt++;//轮数+1}tr[i].ans=a[x];//记录答案}sort(tr+1,tr+q+1,cmp2);//根据输入顺序输出答案for(int i=1;i<=q;i++) printf("%d\n",tr[i].ans);
}
int main()
{int t=1;scanf("%d",&t);while(t--) solve();return 0;
}