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.


-----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 100000$) — 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 $100000$.


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


-----Examples-----

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


-----Note-----

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

$k_1 = 0$ (initial array): $a_3 = 1$;

$k_2 = 1$ (after the $1$-st step): $a_1 = 2$;

$k_3 = 2$ (after the $2$-nd step): $a_2 = 3$;

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

$k_1 = 0$ (initial array): $a_1 = 1$;

$k_2 = 1000000000$: $a_2 = 2$;

Source: codeforces | Difficulty: EASY
Tags: Implementation

Constructive algorithms


Solutions:
import sys
inp = sys.stdin.readline

def solve():
	n = int(inp())
	a = [list(map(int, inp().split()))]
	while True:
		c = [0] * (n + 1)
		for i in a[-1]:
			c[i] += 1
		b = [c[i] for i in a[-1]]
		if b == a[-1]:
			break
		a.append(b)
	ans = []
	for i in range(int(inp())):
		(x, k) = map(int, inp().split())
		ans.append(str(a[min(len(a) - 1, k)][x - 1]))
	print('\n'.join(ans))

def main():
	for i in range(int(inp())):
		solve()
main()


def main():
	import sys
	input = sys.stdin.readline
	M = int(1000000000.0 + 7)
	for _ in range(int(input())):
		n = int(input())
		s = list(map(int, input().split()))
		l = [[]]
		for i in range(n):
			l[0].append(s[i])
		while True:
			d = {}
			l.append([])
			for i in range(n):
				if s[i] in d:
					d[s[i]] += 1
				else:
					d[s[i]] = 1
			for i in range(n):
				s[i] = d[s[i]]
				l[-1].append(s[i])
			if l[-1] == l[-2]:
				break
		for _ in range(int(input())):
			(a, k) = map(int, input().split())
			if k >= len(l):
				print(l[-1][a - 1])
			else:
				print(l[k][a - 1])
main()


from copy import deepcopy
import sys
import math
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = [int(x) for x in sys.stdin.readline().split()]
	m = math.ceil(math.log(n, 2)) + 1
	arrays = []
	occur = {}
	arrays.append(a)
	for i in a:
		if i in occur:
			occur[i] += 1
		else:
			occur[i] = 1
	for __ in range(m):
		cur_a = []
		for i in range(n):
			cur_a.append(occur[arrays[-1][i]])
		occur = {}
		for i in cur_a:
			if i in occur:
				occur[i] += 1
			else:
				occur[i] = 1
		arrays.append(cur_a)
	for __ in range(int(sys.stdin.readline())):
		(x, k) = map(int, sys.stdin.readline().split())
		if k > m:
			print(arrays[m][x - 1])
		else:
			print(arrays[k][x - 1])


for _ in range(int(input())):
	n = int(input())
	a = [list(map(int, input().split()))]
	while True:
		c = [0] * (n + 1)
		for i in a[-1]:
			c[i] += 1
		b = [c[i] for i in a[-1]]
		if b == a[-1]:
			break
		a.append(b)
	ans = []
	for i in range(int(input())):
		(x, k) = map(int, input().split())
		ans.append(str(a[min([len(a) - 1, k])][x - 1]))
	print('\n'.join(ans))


import sys
import bisect
input = sys.stdin.readline

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	arr = [a]
	while True:
		d = {}
		for i in arr[-1]:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		arr.append([d[arr[-1][i]] for i in range(n)])
		for i in range(n):
			if arr[-1][i] != arr[-2][i]:
				break
		else:
			break
	for q in range(int(input())):
		(x, k) = map(int, input().split())
		k = min(k, len(arr) - 1)
		print(arr[k][x - 1])
t = int(input())
for _ in range(t):
	solve()


import sys
from collections import defaultdict
input = sys.stdin.readline

def get_integers():
	return map(int, input().strip().split())
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	arr = [int(x) for x in input().strip().split()]
	storage = []
	storage.append(arr)
	while True:
		counter = defaultdict(int)
		for num in storage[-1]:
			counter[num] += 1
		temp_set = set(storage[-1])
		flag = all([True if counter[key] == key else False for key in temp_set])
		if flag:
			break
		temp_arr = []
		for num in storage[-1]:
			temp_arr.append(counter[num])
		storage.append(temp_arr)
	limit = len(storage) - 1
	q = int(input().strip())
	for _ in range(q):
		(xi, ki) = get_integers()
		if ki > limit:
			ki = limit
		print(storage[ki][xi - 1])


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	d = [*map(int, input().split())]
	q = dict()
	for i in d:
		try:
			q[i] += 1
		except:
			q[i] = 1
	pp = [d.copy()]
	while 1:
		tq = dict()
		for i in range(n):
			d[i] = q[d[i]]
			try:
				tq[d[i]] += 1
			except:
				tq[d[i]] = 1
		if q == tq:
			break
		pp.append(d.copy())
		q = tq
	for _ in range(int(input())):
		(x, k) = map(int, input().split())
		print(pp[-1][x - 1] if k > len(pp) - 1 else pp[k][x - 1])


import sys
from collections import Counter
input = sys.stdin.readline

def trans(l):
	cd = Counter(l)
	t = [0] * len(l)
	for i in range(len(l)):
		t[i] = cd[l[i]]
	return t

def findAll(l):
	ret = []
	ret.append(l)
	while l != trans(l):
		l = trans(l)
		ret.append(l)
	return ret
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	pre = findAll(a)
	qn = int(input())
	for _ in range(qn):
		(x, k) = map(int, input().split())
		if k >= len(pre) - 1:
			print(pre[len(pre) - 1][x - 1])
		else:
			print(pre[k][x - 1])


from sys import stdin
from collections import deque, Counter

def solve():
	for _ in range(int(stdin.readline().strip())):
		N = int(stdin.readline().rstrip())
		A = list(map(int, stdin.readline().rstrip().split()))
		queries = []
		Q = int(stdin.readline().rstrip())
		for i in range(Q):
			(x, k) = map(int, stdin.readline().rstrip().split())
			queries.append((k, x - 1, i))
		queries = deque(sorted(queries))
		results = [0] * Q
		curr_k = 0
		stop = 0
		while len(queries):
			(k, x, i) = queries.popleft()
			if stop or k == curr_k:
				results[i] = A[x]
			else:
				prev_k = curr_k
				curr_k = k
				for _ in range(curr_k - prev_k):
					cnt = Counter(A)
					prev_A = A
					A = [cnt[x] for x in A]
					if A == prev_A:
						stop = 1
						break
				results[i] = A[x]
		print('\n'.join(map(str, results)))
solve()


t = int(input())

def compare(x, y):
	for i in range(len(x)):
		if x[i] != y[i]:
			return False
	return True
out = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = [a]
	i = 1
	while True:
		counter = dict()
		tmp = []
		for x in b[i - 1]:
			if x not in counter:
				counter[x] = b[i - 1].count(x)
			tmp.append(counter[x])
		if compare(tmp, b[i - 1]):
			break
		b.append(tmp)
		i += 1
	q = int(input())
	for j in range(q):
		(x, k) = list(map(int, input().split()))
		out.append(str(b[min(k, i - 1)][x - 1]))
print('\n'.join(out))


import sys
input = sys.stdin.readline
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	c = int(n ** 0.5) + 2
	W = [w]
	for i in range(c):
		s = Counter(w)
		w = [s[i] for i in w]
		W.append(w)
	for i in range(int(input())):
		(x, k) = map(int, input().split())
		k = min(k, c)
		print(W[k][x - 1])


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
inp_vars_int = lambda : map(int, input().split())
inp_list_int = lambda : list(map(int, input().split()))
t = int(input())
for _ in range(t):
	_ = input()
	a = inp_list_int()
	n = len(a)
	q = int(input())
	trans = [a]
	while True:
		a_p = trans[-1]
		cnt = Counter(a_p)
		a_t = [None for _ in range(n)]
		changes = 0
		for (i, ai) in enumerate(a_p):
			a_t[i] = cnt[ai]
			if ai != cnt[ai]:
				changes += 1
		if changes == 0:
			break
		else:
			trans.append(a_t)
	for _ in range(q):
		(x, k) = inp_vars_int()
		if k >= len(trans):
			k = -1
		print(trans[k][x - 1])


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	q = int(input())
	(steps, queries) = ([arr], [])
	for _ in range(q):
		(m1, n1) = map(int, input().split())
		queries.append([m1, n1])
	for i in range(20):
		(d, new) = ({}, steps[-1].copy())
		for a in steps[-1]:
			d[a] = d.get(a, 0) + 1
		for i in range(n):
			new[i] = d[new[i]]
		steps.append(new)
	for (q1, q2) in queries:
		q2 = min(q2, len(steps) - 1)
		print(steps[q2][q1 - 1])


def divine(n, a, qs):
	evolutions = {0: a}
	counts = {0: count(a)}
	evo = 0
	while True:
		new_a = [0] * n
		changed = False
		for i in range(n):
			old_ai = evolutions[evo][i]
			new_ai = counts[evo][old_ai]
			if old_ai != new_ai:
				changed = True
			new_a[i] = new_ai
		evo += 1
		evolutions[evo] = new_a
		counts[evo] = count(new_a)
		if not changed:
			break
	for (xi, ki) in qs:
		ki = min(ki, evo)
		print(evolutions[ki][xi - 1])

def count(a):
	counts = {}
	for ai in a:
		if ai in counts:
			counts[ai] += 1
		else:
			counts[ai] = 1
	return counts
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	q = int(input())
	qs = []
	for _ in range(q):
		(x, k) = map(int, input().split(' '))
		qs += [(x, k)]
	divine(n, a, qs)


def countElements(arrList):
	arrDict = {}
	for arr in arrList:
		if arr not in arrDict.keys():
			arrDict[arr] = 1
		else:
			arrDict[arr] += 1
	return arrDict

def DivineArray(s):
	arrList = list(map(int, s.split(' ')))
	m = int(input())
	x_and_k = []
	for _ in range(m):
		x_and_k.append(list(map(int, input().split(' '))))
	noOfIterations = 0
	for i in range(m):
		if x_and_k[i][1] > noOfIterations:
			noOfIterations = x_and_k[i][1]
	arrTransforms.append(arrList.copy())
	for _ in range(noOfIterations):
		arrDict = countElements(arrList)
		for j in range(len(arrList)):
			arrList[j] = arrDict[arrList[j]]
		arrTransforms.append(arrList.copy())
		if arrTransforms[-1] == arrTransforms[-2]:
			break
	for i in range(len(x_and_k)):
		try:
			print(arrTransforms[x_and_k[i][1]][x_and_k[i][0] - 1])
		except:
			print(arrTransforms[-1][x_and_k[i][0] - 1])
n = int(input())
for _ in range(n):
	arrTransforms = []
	x = int(input())
	DivineArray(input())


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	qi = []
	for _ in range(q):
		qi += [list(map(int, input().split()))]
	ki = [a]
	for _ in range(10 ** 9):
		acpy = a.copy()
		cnt = {i: a.count(i) for i in set(a)}
		for i in range(n):
			acpy[i] = cnt[a[i]]
		if acpy == a:
			break
		a = acpy
		ki.append(acpy)
	for (x, k) in qi:
		try:
			print(ki[k][x - 1])
		except IndexError:
			print(ki[-1][x - 1])
t = int(input())
for _ in range(t):
	solve()


from collections import defaultdict
from functools import reduce
from typing import Counter

def solve(n, nums, q, query):
	state = defaultdict(list)
	max_query = reduce(lambda c, x: max(x[1], c), query, 0)
	steps = 0
	state[steps] = nums
	changing = True
	while steps < max_query and changing:
		counter = Counter(state[steps])
		steps += 1
		state[steps] = [counter[state[steps - 1][i]] for i in range(n)]
		if state[steps] == state[steps - 1]:
			changing = False
	ans = []
	for (index, step) in query:
		if step > steps:
			ans.append(state[steps][index - 1])
		else:
			ans.append(state[step][index - 1])
	return ans
ans = []
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	q = int(input())
	query = [list(map(int, input().split())) for _ in range(q)]
	ans.append(solve(n, nums, q, query))
for a in ans:
	print(*a, sep='\n')


import sys
import collections

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def solve(nums, q):

	def t(nums):
		ans = []
		c = collections.Counter(nums)
		stop = 1
		for i in nums:
			ans.append(c[i])
			if i != c[i]:
				stop = 0
		return (ans, stop)
	for i in range(len(q)):
		q[i] += [i]
	q.sort(key=lambda x: x[1])
	ini = 0
	ans = [None] * len(q)
	stop = 0
	for i in q:
		if stop:
			ans[i[2]] = nums[i[0] - 1]
		else:
			for j in range(ini, i[1]):
				(nums, stop) = t(nums)
				if stop:
					break
			ini = i[1]
			ans[i[2]] = nums[i[0] - 1]
	return ans
T = int(input())
for _ in range(T):
	n = int(input())
	nums = get_ints()
	num_q = int(input())
	q = []
	for i in range(num_q):
		q.append(get_ints())
	ans = solve(nums, q)
	for i in ans:
		print(i)


from collections import Counter
from typing import List, Tuple

def divine_array(xs: List[int], qs: List[Tuple[int, int]]) -> List[int]:
	state = xs
	state_key = 0
	cache = {str(state_key): state}
	final_state = []
	final_state_key = 0
	while final_state != state:
		grps = Counter(state)
		state = [grps[i] for i in state]
		state_key += 1
		cache[str(state_key)] = state
		if state == cache[str(state_key - 1)]:
			final_state = state
			final_state_key = state_key
	results = [cache[str(min(k, final_state_key))][x - 1] for (x, k) in qs]
	return results
results = []
nr_of_tests = int(input())
for _ in range(nr_of_tests):
	xs_len = int(input())
	xs_str = input()
	xs = [int(x) for x in xs_str.split(' ')]
	nr_of_queries = int(input())
	queries = []
	for _ in range(nr_of_queries):
		q_str = input()
		(x, k) = [int(s) for s in q_str.split(' ')]
		queries.append((x, k))
	results += divine_array(xs, queries)
for result in results:
	print(result)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	queries = []
	for query in range(q):
		queries.append(list(map(int, input().split())))
	generations = {0: a}
	for i in range(1, 15):
		gencounter = Counter(generations[i - 1])
		generations[i] = [gencounter[i] for i in generations[i - 1]]
	for (idx, gen) in queries:
		try:
			print(generations[gen][idx - 1])
		except KeyError:
			print(generations[14][idx - 1])


def tranform(arr):
	count = [0] * len(arr)
	res = []
	for i in arr:
		count[i - 1] += 1
	for i in arr:
		res.append(count[i - 1])
	return res
t = int(input())
for test in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	q = int(input())
	p = []
	maxk = 0
	for i in range(q):
		l = list(map(int, input().split()))
		p.append(l)
		maxk = max(maxk, l[1])
	dist = {0: arr}
	for i in range(1, maxk + 1):
		current = dist[i - 1]
		present = tranform(current)
		if current == present:
			maxk = i - 1
			break
		dist[i] = present
	for i in p:
		index = i[0]
		transform = i[1]
		if transform > maxk:
			transform = maxk
		print(dist[transform][index - 1])


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	nums = [int(_) for _ in input().split()]
	q = int(input())
	qs = [[int(_) for _ in input().split()] + [i] for i in range(q)]
	ans = [0] * q
	qs.sort(key=lambda it: it[1])
	(i, j) = (0, 0)
	while j < q and i == qs[j][1]:
		ans[qs[j][2]] = nums[qs[j][0] - 1]
		j += 1
	while j < q and i < qs[j][1]:
		cnt = Counter(nums)
		nums2 = [cnt[z] for z in nums]
		if nums2 == nums:
			break
		nums = nums2
		i += 1
		while j < q and i == qs[j][1]:
			ans[qs[j][2]] = nums[qs[j][0] - 1]
			j += 1
	while j < q:
		ans[qs[j][2]] = nums[qs[j][0] - 1]
		j += 1
	for x in ans:
		print(x)


import sys
import math
from bisect import bisect_right as br
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	arr = int_arr()
	dict = {}
	ch = []
	ch.append(arr)
	temp = arr.copy()
	for k in range(200):
		for i in range(n):
			dict[temp[i]] = dict.get(temp[i], 0) + 1
		for i in range(n):
			temp[i] = dict[temp[i]]
		ch.append(temp)
		temp = temp.copy()
		dict = {}
	for i in range(int(input())):
		(l, m) = int_arr()
		if m >= 200:
			print(ch[200][l - 1])
		else:
			print(ch[m][l - 1])


import sys
sys.setrecursionlimit(10 ** 9)

def cin(datatype):
	return datatype(sys.stdin.readline())

def spin(datatype, retype=None):
	if retype is None:
		return map(datatype, sys.stdin.readline().split())
	return retype(map(datatype, sys.stdin.readline().split()))

def curse(l: list):
	mem = {}
	re = []
	for i in l:
		if i not in mem:
			mem[i] = l.count(i)
		re.append(mem[i])
	return re
T = cin(int)
while T > 0:
	n = cin(int)
	arr = spin(int, list)
	q = cin(int)
	mem = {0: arr[:], 1: curse(arr)}
	rep = -1
	for i in range(q):
		Q = spin(int, list)
		if rep != -1:
			if Q[1] >= rep:
				print(mem[rep - 1][Q[0] - 1])
			else:
				print(mem[Q[1]][Q[0] - 1])
		else:
			for j in range(1, Q[1] + 1):
				if j not in mem:
					mem[j] = curse(mem[j - 1])
				if mem[j] == mem[j - 1]:
					rep = j
					break
			if rep != -1:
				if Q[1] >= rep:
					print(mem[rep - 1][Q[0] - 1])
				else:
					print(mem[Q[1]][Q[0] - 1])
			else:
				print(mem[Q[1]][Q[0] - 1])
	T -= 1


R = lambda : map(int, input().split())

def counter(l):
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	l2 = [d[i] for i in l]
	return l2
(n,) = R()
for i in range(n):
	(length,) = R()
	l = list(R())
	(q,) = R()
	ql = []
	for j in range(q):
		ql.append([j] + list(R()))
	ql.sort(key=lambda x: x[2])
	breaker = False
	Max = ql[-1][-1]
	c = 0
	q3 = []
	l2 = l.copy()
	for k in ql:
		if k[-1] <= Max:
			while c < k[-1]:
				l2 = counter(l)
				if l2 == l:
					breaker = True
				l = l2.copy()
				c += 1
				if breaker:
					Max = c
					break
		q3.append([l2[k[1] - 1], k[0]])
	q3.sort(key=lambda x: x[1])
	for e in q3:
		print(e[0])


def solve(arr, n):
	loop = 0
	arrays = []
	arrays.append(arr)
	while True:
		count = [0 for i in range(n + 1)]
		for x in arr:
			count[x] += 1
		temp = []
		flag = False
		for x in arr:
			y = count[x]
			temp.append(y)
			if x != y:
				flag = True
		if not flag:
			break
		loop += 1
		arr = temp
		arrays.append(arr)
	maxm = loop
	q = int(input())
	for _ in range(q):
		(x, k) = map(int, input().split())
		if k >= maxm:
			print(arrays[-1][x - 1])
		else:
			print(arrays[k][x - 1])
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(arr, n)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	li = []
	li.append(a)
	for i in range(n):
		d = dict()
		for i in range(n):
			if a[i] in d:
				d[a[i]] += 1
			else:
				d[a[i]] = 1
		b = []
		for i in range(n):
			b.append(d[a[i]])
		if b == a:
			li.append(b)
			break
		else:
			li.append(b)
			a = b
	le = len(li)
	q = int(input())
	for i in range(q):
		(x, k) = map(int, input().split())
		if k < le:
			print(li[k][x - 1])
		else:
			print(li[-1][x - 1])


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	last = []
	changes = [a.copy()]
	while True:
		dct = {}
		for el in a:
			dct[el] = dct.get(el, 0) + 1
		for i in range(len(a)):
			a[i] = dct[a[i]]
		changes.append(a.copy())
		if a == last:
			break
		last = a.copy()
	len_array = len(changes)
	for _ in range(q):
		(x, k) = map(int, input().split())
		if k >= len_array:
			print(changes[-1][x - 1])
		else:
			print(changes[k][x - 1])


from collections import Counter
for _ in range(int(input())):
	i = int(input())
	l = list(map(int, input().split()))
	log = []
	log.append(l)
	for x in range(15):
		tem = Counter(l)
		l = [tem[x] for x in l]
		log.append(l)
	for __ in range(int(input())):
		(x, k) = map(int, input().split())
		if k > 15:
			k = 15
		print(log[k][x - 1])


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	res = []
	res.append(arr)
	temp1 = arr.copy()
	temp2 = [0 for i in range(n)]
	while 1:
		k = 0
		cnt = Counter(temp1)
		for j in temp1:
			temp2[k] = cnt[j]
			k += 1
		if temp2 == temp1:
			break
		for j in range(n):
			temp1[j] = temp2[j]
		lst = temp2.copy()
		res.append(lst)
	Q = int(input())
	for q in range(Q):
		(x, k) = map(int, input().split())
		if k < len(res):
			print(res[k][x - 1])
		else:
			print(res[-1][x - 1])


def fun():
	import collections
	for _ in range(int(input())):
		n = int(input())
		v = list(map(int, input().split()))
		arr = []
		temp = v
		while len(arr) == 0 or temp != v:
			arr.append(list(v))
			temp = list(v)
			cnt = collections.Counter(v)
			for i in range(len(v)):
				v[i] = cnt[v[i]]
		q = int(input())
		while q:
			(x, k) = map(int, input().split())
			if k >= len(arr):
				k = len(arr) - 1
			print(arr[k][x - 1])
			q -= 1
	return
fun()


import math
from collections import Counter
import copy
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	q = int(input())
	Dict = {}
	Dict[0] = [i for i in arr]
	change = 0
	ma = 1
	prev = arr
	while True:
		count = Counter(prev)
		temp = []
		change = 0
		for i in range(n):
			if prev[i] != count[prev[i]]:
				change = 1
			temp.append(count[prev[i]])
		if change == 0:
			break
		Dict[ma] = temp
		prev = temp
		ma += 1
	for i in range(q):
		(a, k) = [int(i) for i in input().split()]
		if k >= ma:
			print(prev[a - 1])
		else:
			print(Dict[k][a - 1])


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	l1.append(l)
	for x in range(15):
		t = Counter(l)
		l = [t[x] for x in l]
		l1.append(l)
	y = int(input())
	for __ in range(y):
		(x, k) = map(int, input().split())
		if k > 15:
			k = 15
		print(l1[k][x - 1])


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	ans = [lst]
	while True:
		lst1 = []
		dic = {}
		for j in lst:
			dic[j] = 0
		for j in lst:
			dic[j] += 1
		for h in lst:
			lst1.append(dic[h])
		if lst1 == ans[-1]:
			break
		else:
			ans.append(lst1)
			lst = lst1.copy()
	l = len(ans)
	q = int(input())
	for j in range(q):
		(x, k) = map(int, input().split())
		if k <= l - 1:
			print(ans[k][x - 1])
		else:
			print(ans[-1][x - 1])


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mp = defaultdict(int)
	for i in a:
		mp[i] += 1
	ta = a.copy()
	p = 0
	ans = []
	while True:
		ans.append(a.copy())
		tmp = defaultdict(int)
		for i in range(n):
			a[i] = mp[a[i]]
			tmp[a[i]] += 1
		p += 1
		if ta == a:
			break
		ta = a.copy()
		mp = tmp
	for __ in range(int(input())):
		(x, k) = map(int, input().split())
		if k >= p:
			print(ans[-1][x - 1])
		else:
			print(ans[k][x - 1])


for _ in range(int(input())):
	n = int(input())
	l = []
	l.append(list(map(int, input().split())))
	y = []
	y = l.copy()
	p = 0
	while True:
		f = 2001 * [0]
		for i in l[p]:
			f[i] += 1
		y = []
		for i in range(n):
			y.append(f[l[p][i]])
		l.append(y)
		if l[-1] == l[-2]:
			break
		p += 1
	q = int(input())
	for i in range(q):
		(x, k) = map(int, input().split())
		if k >= len(l):
			print(l[-1][x - 1])
		else:
			print(l[k][x - 1])


import collections
t = int(input())
for i in range(t):
	n = int(input())
	prev = list(map(int, input().split()))
	ck = True
	curr = [0 for i in range(n)]
	k = collections.Counter(prev)
	cnt = 0
	flag = 0
	matrix = [prev]
	while curr != prev:
		for i in range(n):
			if prev[i] in k:
				curr[i] = k[prev[i]]
		matrix.append(curr)
		k = collections.Counter(curr)
		cnt += 1
		if prev == curr:
			break
		else:
			prev = curr
			curr = [0 for i in range(n)]
	q = int(input())
	for i in range(q):
		(ax, k1) = map(int, input().split())
		if k1 >= cnt:
			print(matrix[cnt - 1][ax - 1])
		else:
			print(matrix[k1][ax - 1])


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	q = int(input())
	net = collections.Counter(A)
	table = [A]
	for i in range(10):
		B = []
		for j in table[-1]:
			B.append(net[j])
		table.append(B)
		net = collections.Counter(B)
	for i in range(q):
		(x, k) = map(int, input().split())
		if k < 10:
			print(table[k][x - 1])
		else:
			print(table[10][x - 1])
t = int(input())
while t != 0:
	solve()
	t -= 1


from collections import Counter
import random
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	d = Counter(arr)
	kcc = [arr]
	itcount = 0
	while 1:
		newarr = [d[i] for i in arr]
		kcc.append(newarr)
		if newarr == arr:
			break
		itcount += 1
		arr = newarr
		d = Counter(newarr)
	q = int(input())
	for _1 in range(q):
		(x, k) = map(int, input().split())
		if k < itcount:
			print(kcc[k][x - 1])
		else:
			print(kcc[-1][x - 1])


def freq(arr):
	d = dict()
	for i in arr:
		d[i] = d.get(i, 0) + 1
	return d
for _ in range(int(input())):
	n = int(input())
	a = []
	a.append(list(map(int, input().split())))
	i = 0
	while True:
		d = freq(a[i])
		x = []
		for j in a[i]:
			x.append(d[j])
		a.append(x)
		if a[-1] == a[-2]:
			break
		i += 1
	z = len(a) - 1
	q = int(input())
	for q1 in range(q):
		(x, k) = map(int, input().split())
		if k >= z:
			print(a[z][x - 1])
		else:
			print(a[k][x - 1])


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	prev = -1
	ans = [0, 1]
	p = []
	p += l
	while ans[-1] != ans[-2]:
		d = dict()
		for i in range(len(l)):
			if l[i] in d:
				d[l[i]] += 1
			else:
				d[l[i]] = 1
		ex = []
		for i in range(len(l)):
			l[i] = d[l[i]]
			ex.append(l[i])
		ans.append(ex)
	ans.pop(0)
	ans.pop(0)
	ans.pop(-1)
	ans = [p] + ans
	q = int(input())
	for k in range(q):
		(ind, k) = map(int, input().split())
		if k >= len(ans):
			k = -1
		print(ans[k][ind - 1])


import sys
from collections import Counter
_DEBUG = False
if _DEBUG:
	fd = open('input.txt', 'r')
	sys.stdin = fd

def find_next(A, n):
	d = Counter(A)
	Anext = A.copy()
	for i in range(n):
		Anext[i] = d[A[i]]
	if Anext == A:
		return (Anext, True)
	else:
		return (Anext, False)
for t in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	Acopy = A.copy()
	states = []
	states.append(A)
	i = 0
	while True:
		(A, flag) = find_next(A, n)
		if flag:
			break
		else:
			states.append(A)
		i += 1
	(nrows, ncols) = (len(states), len(states[0]))
	Q = int(input())
	for q in range(Q):
		tup = input().split()
		(j, i) = map(int, tup)
		if i < nrows:
			print(states[i][j - 1])
		else:
			print(states[nrows - 1][j - 1])
fd.close() if _DEBUG else None


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	di = Counter(a)
	arr = [a]
	a1 = []
	for i in range(n):
		a1.append(di[a[i]])
	arr.append(a1)
	i = 1
	while True:
		di = Counter(arr[i])
		a2 = []
		for j in range(n):
			a2.append(di[arr[i][j]])
		if a2 == arr[-1]:
			break
		arr.append(a2)
		i += 1
	size = len(arr)
	q = int(input())
	for i in range(q):
		(x, k) = map(int, input().split())
		if k < size:
			print(arr[k][x - 1])
		else:
			print(arr[-1][x - 1])


import collections as coll
for testcase in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	q = int(input())
	log = [a]
	for i in range(1, 16):
		freq = coll.Counter(log[i - 1])
		log.append([freq[log[i - 1][j]] for j in range(n)])
	for i in range(q):
		(x, k) = [int(_) for _ in input().split(' ')]
		if k > 15:
			k = 15
		print(log[k][x - 1])


import math
import random
from collections import Counter
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	q = int(input())
	cnt = Counter(arr)
	query = []
	query += [arr]
	bool = False
	iter = 0
	iter2 = 0
	prevarr = arr[:]
	xnt = 0
	querarr = []
	querarr += [arr]
	while True:
		newarr = []
		for i in range(n):
			newarr += [cnt[prevarr[i]]]
		if newarr == prevarr:
			break
		querarr += [newarr]
		xnt += 1
		cnt = Counter(newarr)
		prevarr = newarr[:]
	for i in range(q):
		(x, k) = map(int, input().split())
		if k == 0:
			print(arr[x - 1])
			continue
		if k >= xnt:
			print(querarr[xnt][x - 1])
			continue
		if k < xnt:
			print(querarr[k][x - 1])
			continue


from collections import *
for _ in range(int(input())):
	input()
	l = list(map(int, input().split()))
	d = {0: l}
	for i in range(1, 16):
		c = Counter(d[i - 1])
		d[i] = [c[j] for j in d[i - 1]]
	for i in range(int(input())):
		(x, y) = map(int, input().split())
		print(d[y][x - 1] if y < 15 else d[15][x - 1])


T = int(input())
for test in range(1, T + 1):
	N = int(input())
	A = [int(S) for S in input().split()]
	status = [A[:]]
	for step in range(1, N + 1):
		newStat = status[-1][:]
		count = {}
		for num in newStat:
			if num not in count:
				count[num] = 0
			count[num] += 1
		for idx in range(len(newStat)):
			newStat[idx] = count[newStat[idx]]
		if newStat == status[-1]:
			break
		status.append(newStat)
	queries = int(input())
	for query in range(queries):
		(idx, after) = [int(S) for S in input().split()]
		if after < len(status):
			print(status[after][idx - 1])
		else:
			print(status[-1][idx - 1])


import copy

def arr_eq(arr1, arr2):
	for (a, b) in zip(arr1, arr2):
		if a != b:
			return False
	return True

def do():
	n = int(input())
	arr = [int(n) for n in input().split()]
	hist = [copy.copy(arr)]
	while True:
		vals = {}
		for n in arr:
			if n not in vals:
				vals[n] = 0
			vals[n] += 1
		new_arr = [vals[n] for n in arr]
		if arr_eq(new_arr, hist[-1]):
			break
		hist.append(copy.copy(new_arr))
		arr = new_arr
	q = int(input())
	while q > 0:
		temp = [int(i) for i in input().split()]
		(x, k) = (temp[0] - 1, temp[1])
		if k < len(hist):
			print(hist[k][x])
		else:
			print(hist[-1][x])
		q -= 1
t = int(input())
while t > 0:
	do()
	t -= 1


from collections import defaultdict
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = []
	while True:
		d = defaultdict(lambda : 0)
		ans.append(a.copy())
		for j in a:
			d[j] += 1
		eq = True
		for j in d.keys():
			if d[j] != j:
				eq = False
		for j in range(n):
			a[j] = d[a[j]]
		if eq:
			ans.append(a)
			break
	l = len(ans)
	for j in range(int(input())):
		(x, k) = map(int, input().split())
		if k < l:
			print(ans[k][x - 1])
		else:
			print(ans[-1][x - 1])


def fre(arr, n):
	d = dict()
	for i in arr:
		d[i] = d.get(i, 0) + 1
	return d
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	arr = []
	arr.append(l)
	while True:
		d = fre(arr[-1], n)
		l = []
		for i in arr[-1]:
			l.append(d[i])
		arr.append(l)
		if arr[-1] == arr[-2]:
			break
	for abcd in range(int(input())):
		(x, k) = map(int, input().split())
		if k >= len(arr) - 1:
			print(arr[len(arr) - 1][x - 1])
		else:
			print(arr[k][x - 1])


import copy
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	temp = copy.deepcopy(a)
	s = [temp]
	while True:
		b = 0
		dic = {}
		for x in a:
			if x in dic:
				dic[x] += 1
			else:
				dic[x] = 1
		for i in range(n):
			if a[i] != dic[a[i]]:
				b = 1
			a[i] = dic[a[i]]
		s.append(copy.deepcopy(a))
		if b == 0:
			break
	for i in range(q):
		(x, k) = map(int, input().split())
		if k < len(s):
			print(s[k][x - 1])
		else:
			print(s[-1][x - 1])
	t -= 1


t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	q = int(input())
	grid = [list1]
	while 1:
		dict1 = {}
		for i in range(0, n):
			if list1[i] in dict1:
				dict1[list1[i]] += 1
			else:
				dict1[list1[i]] = 1
		new = []
		for i in range(0, n):
			new.append(dict1[list1[i]])
		if new != grid[len(grid) - 1]:
			grid.append(new)
			list1 = new
		else:
			break
	for i in range(0, q):
		inputs1 = [int(num) for num in input().split()]
		k = inputs1[1]
		if k < len(grid):
			print(grid[k][inputs1[0] - 1])
		else:
			print(grid[len(grid) - 1][inputs1[0] - 1])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	arr = []
	cr = []
	for i in range(n):
		cr.append(a[i])
	arr.append(a)
	while True:
		ar = [0] * (n + 5)
		for i in range(n):
			ar[cr[i]] += 1
		for i in range(n):
			cr[i] = ar[cr[i]]
		if cr == arr[-1]:
			break
		else:
			ex = []
			for i in cr:
				ex.append(i)
			arr.append(ex)
	n1 = len(arr)
	q = int(input())
	for _ in range(q):
		(x, k) = map(int, input().split())
		if k > n1 - 1:
			k = n1 - 1
		print(arr[k][x - 1])


def getarr(d, n):
	arr = [0 for i in range(n)]
	for k in d.keys():
		for v in d[k]:
			arr[v] = k
	return arr

def f(arr):
	d = {}
	for i in range(len(arr)):
		if arr[i] in d:
			d[arr[i]].append(i)
		else:
			d[arr[i]] = [i]
	change = True
	iter = 0
	ans = {}
	n = len(arr)
	while change:
		ans[iter] = getarr(d, n)
		flag = False
		d1 = {}
		for k in d.keys():
			count = len(d[k])
			if count != k:
				flag = True
			if count not in d1:
				d1[count] = d[k]
			else:
				d1[count] = d1[count] + d[k]
		if flag:
			change = True
			iter += 1
		else:
			change = False
		d = d1
	return {'iter': iter, 'final': getarr(d, n), 'arr': ans}
res = f([2, 1, 1, 4, 3, 1, 2])
tc = int(input())
for _ in range(tc):
	n = int(input())
	arr = list(map(int, input().split()))
	q = int(input())
	result = f(arr)
	n_iter = result['iter']
	final_arr = result['final']
	inter = result['arr']
	for q1 in range(q):
		(a, b) = list(map(int, input().split()))
		a -= 1
		if b >= n_iter:
			print(final_arr[a])
		else:
			print(inter[b][a])


from collections import defaultdict, Counter
from queue import PriorityQueue, Queue
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	transformation = [a]
	u = Counter(a)
	while True:
		change = False
		b = [0] * n
		for i in range(n):
			if u[transformation[-1][i]] != transformation[-1][i]:
				b[i] = u[transformation[-1][i]]
				change = True
			else:
				b[i] = transformation[-1][i]
		if change:
			transformation.append(b)
			u = Counter(b)
		else:
			break
	for _ in range(q):
		(x, k) = map(int, input().split())
		print(transformation[min(len(transformation) - 1, k)][x - 1])


from collections import Counter

def mgc(a):
	fans = [a]
	ans = []
	while True:
		b = Counter(a)
		ans = []
		for i in a:
			ans.append(b[i])
		if fans[-1] == ans:
			break
		fans.append(ans)
		a = ans
	return fans

def query(fans, x, k):
	if k >= len(fans):
		return fans[-1][x - 1]
	return fans[k][x - 1]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	fans = mgc(a)
	for i in range(q):
		(x, k) = map(int, input().split())
		print(query(fans, x, k))


from collections import Counter

def test_case():
	n = input()
	a = [int(i) for i in input().split()]
	pos = dict()
	steps = [a]
	seen = set(a)
	while True:
		count = Counter(a)
		b = tuple([count[i] for i in a])
		if b in seen:
			break
		seen.add(b)
		pos[b] = len(steps)
		steps.append(b)
		a = tuple(b)
	q = int(input())
	posa = pos[a]
	for i in range(q):
		(x, k) = (int(i) for i in input().split())
		if k <= posa:
			print(steps[k][x - 1])
		else:
			k -= posa
			k %= len(steps) - posa
			print(steps[k + posa][x - 1])

def main():
	tc = int(input())
	for i in range(tc):
		test_case()
main()


from copy import deepcopy as copy
for _ in range(int(input())):
	n = int(input())
	f = [0 for i in range(n + 1)]
	x = list(map(int, input().split()))
	for i in x:
		f[i] += 1
	ans = [x]
	while 1:
		f2 = [0 for i in range(n + 1)]
		y = [0 for i in range(n)]
		for i in range(n):
			y[i] = f[x[i]]
			f2[y[i]] += 1
		f = f2
		if x == y:
			break
		x = y
		ans += [y]
	q = int(input())
	for i in range(q):
		(iq, kq) = map(int, input().split())
		if kq >= len(ans):
			kq = -1
		print(ans[kq][iq - 1])


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	line = [int(ch) for ch in input().split()]
	q = int(input())
	(l, line1) = ([line], [])
	while True:
		b = Counter(line)
		line1 = []
		for j in line:
			line1.append(b[j])
		if l[-1] == line1:
			break
		l.append(line1)
		line = line1
	for j in range(q):
		(x, y) = map(int, input().split())
		if y >= len(l):
			print(l[-1][x - 1])
		else:
			print(l[y][x - 1])


def change(astring):
	alist = [astring]
	while True:
		adict = {i: astring.count(i) for i in set(astring)}
		astring2 = [adict[i] for i in astring]
		if astring2 == astring:
			break
		astring = astring2
		alist.append(astring)
	return alist
test = int(input())
for _ in range(test):
	n = int(input())
	astring = list(map(int, input().split()))
	alist = change(astring)
	count = len(alist)
	q = int(input())
	for _ in range(q):
		(x, k) = map(int, input().split())
		print(alist[min(k, count - 1)][x - 1])


t = int(input())
for ii in range(t):
	n = int(input())
	aa = []
	a = list(map(int, input().split()))
	l3 = list()

	def fun(l1, l2):
		l2 = []
		d = {}
		for i in l1:
			if i in d.keys():
				d[i] += 1
			else:
				d[i] = 1
		for i in l1:
			l2.append(d[i])
		l3.append(l1)
		if l1 == l2:
			return
		else:
			return fun(l2, l2)
	q = int(input())
	fun(a, [])
	for iii in range(q):
		(x, y) = list(map(int, input().split()))
		if y >= len(l3):
			print(l3[-1][x - 1])
		else:
			print(l3[y][x - 1])


from collections import Counter

def ca(array, l, a=True):
	while a == True:
		ll = dict(Counter(array))
		for i in range(0, len(array)):
			array[i] = ll[array[i]]
		gl[l] = array[:]
		if l > 2:
			if gl[l - 1] == gl[l]:
				a = False
		l += 1
for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	l = 1
	gl = {0: array[:]}
	array = ca(array, l, a=True)
	gl = list(gl.values())
	for __ in range(int(input())):
		(a, b) = map(int, input().split())
		if len(gl) - 1 < b:
			cc = gl[-1][a - 1]
			print(cc)
		else:
			cc = gl[b][a - 1]
			print(cc)


t = int(input())
while t:
	n = int(input())
	L = input().split()
	f = [0]
	g = [0]
	c = 0
	fin = [[]]
	for i in range(n):
		f.append(0)
		g.append(0)
		L[i] = int(L[i])
		fin[-1].append(L[i])
	for i in range(n):
		f[L[i]] += 1
	for i in range(1, n + 1):
		g[f[i]] += 1
	for i in range(1, n + 1):
		if i * g[i] != 0:
			if i * g[i] != i:
				g[i * g[i]] += 1
				g[i] = 0
				c += 1
	for j in range(c + 1):
		for i in range(n):
			L[i] = f[L[i]]
		for i in range(n + 1):
			f[i] = 0
		for i in range(n):
			f[L[i]] += 1
		fin.append([])
		for i in range(n):
			fin[-1].append(L[i])
	q = int(input())
	while q:
		(x, k) = [int(i) for i in input().split()]
		x -= 1
		if k <= c:
			print(fin[k][x])
		else:
			print(fin[-1][x])
		q -= 1
	t -= 1


from collections import *
R = lambda : map(int, input().split())
(t,) = R()
while t:
	t -= 1
	R()
	a = ([*R()],)
	(q,) = R()
	for _ in [0] * 11:
		c = Counter((b := a[-1]))
		a += ([c[x] for x in b],)
	while q:
		q -= 1
		(x, k) = R()
		print(a[min(k, 10)][x - 1])


for _ in range(int(input())):
	n = int(input())
	xd = []
	xd += [list(map(int, input().split()))]
	while True:
		xd += [[]]
		temp = {}
		for i in range(n):
			temp[xd[-2][i]] = temp.setdefault(xd[-2][i], 0) + 1
		for i in range(n):
			xd[-1] += [temp[xd[-2][i]]]
		if xd[-1] == xd[-2]:
			break
	for _ in range(int(input())):
		(x, k) = map(int, input().split())
		if k >= len(xd):
			print(xd[-1][x - 1])
		else:
			print(xd[k][x - 1])


from collections import defaultdict, deque
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	adj = []
	steps = 0
	while True:
		prev = [i for i in a]
		f = [0 for i in range(n + 1)]
		adj.append(prev)
		for x in a:
			f[x] += 1
		for i in range(n):
			a[i] = f[a[i]]
		if a == prev:
			break
		steps += 1
	q = int(input())
	for i in range(q):
		(x, k) = map(int, input().split())
		x -= 1
		k = min(steps, k)
		print(adj[k][x])


from collections import Counter

def check_equal(a1, a2, n):
	for i in range(n):
		if a1[i] != a2[i]:
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	states = [arr]
	si = 0
	while True:
		st = states[si]
		d = Counter(st)
		next_state = [0] * n
		for i in range(n):
			next_state[i] = d[st[i]]
		states.append(next_state)
		si += 1
		if check_equal(next_state, st, n):
			break
	q = int(input())
	for ii in range(q):
		(x, k) = map(int, input().split())
		k = min(k, len(states) - 1)
		print(states[k][x - 1])


T = int(input().strip())
for t in range(T):
	n = int(input().strip())
	array = list(map(int, input().strip().split()))
	q = int(input().strip())
	table = [array]
	while True:
		last = table[-1]
		freq = {}
		for num in last:
			if num not in freq:
				freq[num] = 0
			freq[num] += 1
		finished = True
		for num in freq:
			if freq[num] != num:
				finished = False
				break
		if finished:
			break
		next_array = []
		for num in last:
			next_array.append(freq[num])
		table.append(next_array)
	for query in range(q):
		(x, k) = list(map(int, input().strip().split()))
		x -= 1
		if k >= len(table):
			print(table[-1][x])
		else:
			print(table[k][x])


aCount = int(input())
for a in range(aCount):
	aSize = int(input())
	array = list(map(int, input().split()))
	qCount = int(input())
	transforms = [array]
	repeatTransformIndex = 0
	for q in range(qCount):
		s = input().split()
		Xi = int(s[0])
		Ki = int(s[1])
		lastTransformIndex = len(transforms) - 1
		if Ki > lastTransformIndex and repeatTransformIndex == 0:
			lastTransform = transforms[lastTransformIndex]
			for k in range(lastTransformIndex, Ki):
				vCounts = {}
				for v in lastTransform:
					if v in vCounts:
						vCounts[v] = vCounts[v] + 1
					else:
						vCounts[v] = 1
				newTransform = []
				for v in lastTransform:
					newTransform.append(vCounts[v])
				if newTransform != lastTransform:
					transforms.append(newTransform)
					lastTransform = newTransform
				else:
					repeatTransformIndex = k
					break
		if repeatTransformIndex > 0:
			print(transforms[min(Ki, repeatTransformIndex)][Xi - 1])
		else:
			print(transforms[min(Ki, len(transforms) - 1)][Xi - 1])


from collections import Counter

def read_nums():
	return [int(x) for x in input().split()]

def run_step(nums):
	res = []
	counter = Counter(nums)
	for num in nums:
		res.append(counter[num])
	return res

def run_steps(nums):
	res = [nums.copy()]
	while True:
		new_arr = run_step(res[-1])
		if new_arr == res[-1]:
			break
		res.append(new_arr)
	return res

def solve():
	(n,) = read_nums()
	nums = read_nums()
	answers = run_steps(nums)
	(q,) = read_nums()
	for _ in range(q):
		(x, k) = read_nums()
		k = min(k, len(answers) - 1)
		print(answers[k][x - 1])

def main():
	(t,) = read_nums()
	for _ in range(t):
		solve()
main()


from collections import Counter
for i in range(int(input())):
	n = int(input())
	a = input().split()
	nw_lst = []
	nw_lst.append(a)
	dct = Counter(a)
	while True:
		lst2 = []
		for i in nw_lst[-1]:
			lst2.append(dct[i])
		if lst2 == nw_lst[-1]:
			break
		else:
			dct = Counter(lst2)
			nw_lst.append(lst2)
	q = int(input())
	for i in range(q):
		(x, k) = map(int, input().split())
		t = len(nw_lst)
		if k < t:
			print(nw_lst[k][x - 1])
		else:
			print(nw_lst[-1][x - 1])


n_cases = int(input())
for j in range(n_cases):
	arr_len = int(input())
	arr_s = input()
	q_num = int(input())
	arr = []
	steps = []
	for nino in arr_s.split(' '):
		arr.append(int(nino))
	steps += arr
	idrb = True
	while idrb:
		idrb = False
		arr_k = {}
		for c in range(1, arr_len + 1):
			arr_k[c] = 0
		for b in arr:
			arr_k[b] += 1
		for s in range(arr_len):
			key = arr[s]
			if arr_k[key] != key:
				idrb = True
				arr[s] = arr_k[key]
		if idrb:
			steps += arr
	for d in range(q_num):
		q = input().split(' ')
		a = int(q[0])
		k = int(q[1])
		leno = int(len(steps) / arr_len)
		if k >= leno:
			k = leno - 1
		index = k * arr_len + (a - 1)
		print(str(steps[index]))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = [[0 for i in range(n)] for j in range(50)]
	a = list(map(int, input().strip().split()))
	arr[0] = a.copy()
	for i in range(1, 50):
		mp = [0 for i in range(n + 1)]
		for x in arr[i - 1]:
			mp[x] += 1
		for j in range(n):
			arr[i][j] = mp[arr[i - 1][j]]
	q = int(input())
	for i in range(q):
		(id, k) = map(int, input().strip().split())
		k = min(k, 45)
		print(arr[k][id - 1])


class Solution:

	def __init__(self, arr=None):
		self.initalArr = []
		self.currentDict = {}
		for i in arr:
			if i in self.currentDict:
				self.currentDict[i] += 1
			else:
				self.currentDict[i] = 1
		if arr:
			self.initalArr.append(arr)
			for j in range(20):
				new = []
				for i in range(len(self.initalArr[-1])):
					new.append(self.currentDict[self.initalArr[-1][i]])
				self.initalArr.append(new)
				newDict = {}
				for i in new:
					if i in newDict:
						newDict[i] += 1
					else:
						newDict[i] = 1
				self.currentDict = newDict

	def transformation(self, x: int, k: int):
		if len(self.initalArr) > k:
			return self.initalArr[k][x - 1]
		else:
			return self.initalArr[-1][x - 1]
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	obj = Solution(arr)
	query = int(input())
	for __ in range(query):
		(x, k) = list(map(int, input().split()))
		print(obj.transformation(x, k))


t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for i in range(n):
		try:
			d[arr[i]] += 1
		except:
			d[arr[i]] = 1
	res = [arr]
	tmp = []
	for i in range(n):
		tmp.append(d[arr[i]])
	res.append(tmp)
	while True:
		d = {}
		for i in range(n):
			try:
				d[res[-1][i]] += 1
			except:
				d[res[-1][i]] = 1
		tmp = []
		for i in range(n):
			tmp.append(d[res[-1][i]])
		if tmp == res[-1]:
			break
		res.append(tmp)
	q = int(input())
	for j in range(q):
		(x, k) = map(int, input().split())
		try:
			print(res[k][x - 1])
		except:
			print(res[-1][x - 1])


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	t = [s.copy()]
	while True:
		c = Counter(s)
		for i in range(n):
			s[i] = c[s[i]]
		if s == t[-1]:
			break
		else:
			t += [s.copy()]
	mxlen = len(t) - 1
	for i in range(int(input())):
		(q, w) = map(int, input().split())
		w = min(w, mxlen)
		print(t[w][q - 1])


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	k = int(input())
	track = []
	track.append(arr[:])
	for _ in range(15):
		dp = {}
		for i in arr:
			if i in dp:
				dp[i] += 1
			else:
				dp[i] = 1
		for j in range(n):
			arr[j] = dp[arr[j]]
		track.append(arr[:])
	for _ in range(k):
		try:
			(x, y) = map(int, input().split())
			print(track[y][x - 1])
		except:
			print(track[-1][x - 1])