B'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 , 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: 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. 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 a_1, a_2, ... , a_n ( 1 <= a_i <= n ) -- the initial values of array a . The third line of each test case contains a single integer q ( 1 <= q <= 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 <= x_i <= n ; 0 <= k_i <= 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 '...