Chef has an array A of length N.

In one operation, Chef can choose any [subsequence] of the array and any integer X and then add X to all the elements of the chosen subsequence.

Determine the minimum number of operations required to make all the elements of the array distinct.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N — the length of Array A.
- Next line contains N space-separated integers A_{1}, A_{2}, A_{3}, \dots, A_{N} - denoting the array A.

------ Output Format ------ 

For each test case, output the minimum number of operations required to make all the elements distinct.

------ Constraints ------ 

$1 ≤ T ≤ 4000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases do not exceed $3 \cdot 10^{5}$

----- Sample Input 1 ------ 
4
3
3 3 3
6
1 3 2 1 2 2
4
1 2 1 2
5
1 3 2 4 6

----- Sample Output 1 ------ 
2
2
1
0

----- explanation 1 ------ 
Test case $1$:
- Operation $1$: Choose the subsequence $\{A_{1}\}$ and add $X = 1$ to the elements. The array becomes $A = [4, 3, 3]$.
- Operation $2$: Choose the subsequence $\{A_{2}\}$ and add $X = 2$ to the elements. The array becomes $A = [4, 5, 3]$.

Thus, we require, minimum $2$ operations to make all the elements distinct.

Test case $2$:
- Operation $1$: Choose the subsequence $\{A_{1}, A_{6}\}$ and add $X = 4$ to the elements. The array becomes $A = [5, 3, 2, 1, 2, 6]$.
- Operation $2$: Choose the subsequence $\{A_{3}\}$ and add $X = 5$ to the elements. The array becomes $A = [5, 3, 7, 1, 2, 6]$.

Thus, we require, minimum $2$ operations to make all the elements distinct.

Test case $3$:
- Operation $1$: Choose the subsequence $\{A_{3}, A_{4}\}$ and add $X = 2$ to the elements. The array becomes $A = [1, 2, 3, 4]$.

Thus, we require, minimum $1$ operation to make all the elements distinct.

Test case $4$: All the elements are distinct. We need zero operations.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
import math
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	print(math.ceil(math.log(max(Counter(a).values()), 2)))


import math
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	x = max(d.values())
	print(math.ceil(math.log(x, 2)))


from statistics import mode
import math
t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	l = list(map(int, input().split()))
	m = mode(l)
	a = l.count(m) - 1
	if a == 0:
		print(0)
	else:
		print(len(bin(a)) - 2)


from collections import Counter
import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ac = Counter(a)
	al = list(ac.values())
	print(math.ceil(math.log2(max(al))))


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	dic = {}
	for i in A:
		if i not in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	mx = max(dic.values())
	count = 0
	while 2 ** count < mx:
		count += 1
	print(count)


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		l = [int(x) for x in input().split()]
		d = {}
		for i in l:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		l = []
		m = 0
		for (i, j) in d.items():
			if j > m:
				m = j
		c = 0
		while m > 1:
			if m % 2 == 0:
				m = m // 2
			else:
				m = (m + 1) // 2
			c += 1
		print(c)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	c = max(d.values())
	k = 0
	while 2 ** k < c:
		k += 1
	print(k)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for x in a:
		if x not in d:
			d[x] = 0
		d[x] += 1
	m = max(d.values())
	k = 0
	while 2 ** k < m:
		k += 1
	print(k)


import statistics
t = int(input())
for i in range(t):
	input_size = int(input())
	x = list(map(int, input().split()))
	ans = 0
	v = statistics.mode(x)
	count = x.count(v)
	while count > 1:
		if count % 2 == 1:
			count = (count + 1) / 2
		else:
			count = count / 2
		ans = ans + 1
	print(ans)


from collections import Counter
import math
T = int(input())
for _ in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	C = Counter(L)
	M = max(C.values())
	count = 0
	while M > 1:
		M = math.ceil(M / 2)
		count = count + 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = {}
	for i in a:
		if i not in f:
			f[i] = 1
		else:
			f[i] += 1
	m = 0
	for i in f:
		if f[i] > m:
			m = f[i]
	count = 0
	while m > 1:
		if m % 2:
			m = (m + 1) // 2
		else:
			m = m // 2
		count += 1
	print(count)


t = int(input())
while t:
	a = int(input())
	d = {}
	l = list(map(int, input().split()))
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	count = 0
	x = max(list(d.values()))
	while x > 1:
		if x % 2 == 0:
			x = x // 2
		else:
			x = (x + 1) // 2
		count += 1
	print(count)
	t -= 1


import math
T = int(input())
for t in range(T):
	N = int(input())
	l = map(int, input().split())
	dictS = dict()
	maxNum = 0
	maxV = 1
	for el in l:
		if not el in dictS:
			dictS[el] = 1
		else:
			dictS[el] += 1
			if dictS[el] > maxV:
				maxNum = el
				maxV = dictS[el]
	print(math.ceil(math.log2(maxV)))


t = int(input())
import math
for _ in range(t):
	n = int(input())
	arr = list(input().split())
	check = {}
	for x in arr:
		if x in check:
			check[x] += 1
		else:
			check[x] = 1
	ans = max(check.values())
	print(math.ceil(math.log2(ans)))


t = int(input())
for i in range(t):
	n = int(input())
	x = 0
	count = 0
	list2 = []
	list1 = list(map(int, input().split()))
	dict1 = {}
	for i in list1:
		if i not in dict1:
			dict1[i] = 1
		else:
			dict1[i] = dict1[i] + 1
	for i in dict1.values():
		list2.append(i)
	x = max(list2)
	while x > 1:
		if x % 2 == 0:
			x = x // 2
		else:
			x = (x + 1) // 2
		count += 1
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	d = {}
	for j in l1:
		if j not in d:
			d[j] = 1
		else:
			d[j] += 1
	n = max(list(d.values()))
	ans = 0
	while n > 1:
		ans += 1
		if n % 2 == 0:
			n = n // 2
		else:
			n = (n + 1) // 2
	print(ans)


import math
t = int(input())
while t:
	t = t - 1
	n = int(input())
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	a.sort()
	max = 0
	count = 1
	for i in range(1, n):
		if a[i - 1] == a[i]:
			count = count + 1
		else:
			if max <= count:
				max = count
			count = 1
	if max <= count:
		max = count
	print(math.ceil(math.log2(max)))


from collections import Counter
import math as m
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = max(Counter(l).values()) - 1
	if x == 0:
		print(0)
	else:
		print(int(m.ceil(m.log(max(Counter(l).values()), 2))))


import math
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l = [int(i) for i in input().split()]
	d = {}
	unique = 1
	largest = 0
	for i in l:
		d[i] = d.get(i, 0) + 1
		if unique == 1 and d[i] > 1:
			unique = 0
		if d[i] > largest:
			largest = d[i]
	if unique == 1:
		print('0')
	else:
		print(int(math.ceil(math.log(largest, 2))))


from math import ceil, log2
from statistics import mode
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c = mode(arr)
	print(ceil(log2(arr.count(c))))


import collections
import math
import numpy as np

def count(array):
	counter = collections.Counter(array)
	max_n = max(list(counter.values()))
	return math.ceil(np.log2(max_n))
n = int(input())
for a in range(0, n):
	length = int(input())
	array = list(map(int, input().split()))
	print(count(array))


def abc(n):
	if n == 1:
		return 0
	elif n & 1:
		cnt = 1 + abc(n // 2 + 1)
	else:
		cnt = 1 + abc(n // 2)
	return cnt
for i in range(int(input())):
	(max_count_z, n_z) = (0, int(input()))
	arr_z = [int(ele_z) for ele_z in input().split()]
	dict1_z_z = {}
	for ele in arr_z:
		if dict1_z_z.get(ele) is None:
			dict1_z_z[ele] = 0
		dict1_z_z[ele] += 1
		max_count_z = max(max_count_z, dict1_z_z[ele])
	print(abc(max_count_z))


import math

def subseq(arr):
	comp = dict()
	for val in arr:
		if val not in comp:
			comp[val] = 1
		else:
			comp[val] += 1
	max_cnt = max(comp.values())
	if max_cnt == 1:
		return 0
	return math.ceil(math.log2(max_cnt))
T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	print(subseq(arr))


import math
from collections import defaultdict
for _ in range(int(input())):
	d = defaultdict(lambda : 0)
	n = int(input())
	a = list(map(int, input().split()))
	ue = []
	for ele in a:
		if d[ele] == 0:
			ue.append(ele)
		d[ele] += 1
	m = 0
	for uele in ue:
		m = max(m, d[uele])
	ans = 0
	while m > 1:
		ans += 1
		if m % 2 == 0:
			m = m // 2
		else:
			m = (m + 1) // 2
	print(ans)


import sys
import math

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

def fast_out(n):
	sys.stdout.write(str(n) + '\n')
T = int(input())
for n1 in range(T):
	n = int(input())
	A = list(get_ints())
	d = dict()
	for i in A:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	c = max(d.values())
	if c == 1:
		print(0)
	else:
		print(math.ceil(math.log(c, 2)))


import math
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = Counter(a)
	c = max(b.values())
	if c != 1:
		print(math.ceil(math.log(c, 2)))
	else:
		print(0)


import numpy as np
import math
y = int(input())
for z in range(y):
	noOfElements = int(input())
	temp = [int(x) for x in input().split()]
	(uniqueArr, count) = np.unique(temp, return_counts=True)
	if max(count) - 1 == 0:
		print('0')
	else:
		print(int(math.log(max(count) - 1) / math.log(2)) + 1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dict = {}
	m = 0
	for i in a:
		dict[i] = dict.get(i, 0) + 1
	for key in dict:
		if dict[key] > 1:
			a = len(bin(dict[key] - 1)[2:])
			m = max(m, a)
	print(m)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for i in arr:
		d[i] = d.get(i, 0) + 1
	maxi = 0
	for key in d:
		if d[key] > 1:
			oper = len(bin(d[key] - 1)[2:])
			maxi = max(maxi, oper)
	print(maxi)


from math import ceil, log2
from statistics import mode
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = mode(a)
	print(ceil(log2(a.count(p))))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	d = {}
	l1 = []
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	n = max(list(d.values()))
	c = 0
	while n > 1:
		if n % 2 == 0:
			n = n // 2
		else:
			n = (n + 1) // 2
		c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dic = {}
	ans = 0
	flag = True
	for i in arr:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	n = max(list(dic.values()))
	while n > 1:
		if n % 2 == 0:
			ans += 1
			n = n // 2
		else:
			ans += 1
			n = (n + 1) // 2
	print(ans)


from collections import Counter
from math import log2, ceil
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = Counter(a)
	x = max(x.values())
	print(ceil(log2(x)))


from math import log2, ceil
for _ in range(int(input())):
	input()
	arr = map(int, input().split())
	count = {}
	for i in arr:
		if i in count.keys():
			count[i] += 1
		else:
			count[i] = 1
	a = max(count.values())
	print(ceil(log2(a)))


from itertools import count
from typing import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	cout = max(Counter(l).values())
	while cout > 1:
		if cout % 2 == 0:
			cout = cout // 2
			ans += 1
		else:
			cout = (cout + 1) // 2
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	count = 0
	ans = 0
	for i in l:
		d[i] = d.get(i, 0) + 1
		count = max(count, d[i])
	while count > 1:
		if count % 2 == 0:
			count = count // 2
		else:
			count = (count + 1) // 2
		ans += 1
	print(ans)


from math import log, ceil
from collections import Counter
test = int(input())
while test:
	n = int(input())
	a = [int(x) for x in input().split()]
	ct = Counter(a)
	maxi = max(list(ct.values()))
	print(ceil(log(maxi, 2)))
	test -= 1


from collections import Counter
from math import floor
t = int(input())
while t > 0:
	numbers = int(input())
	arr = list(map(int, input().split()))
	freq = Counter(arr)
	maxFrequency = 0
	for x in freq:
		if freq[x] > maxFrequency:
			maxFrequency = freq[x]
	count = 0
	while maxFrequency > 1:
		if maxFrequency % 2 == 0:
			maxFrequency = floor(maxFrequency / 2)
			count += 1
		else:
			maxFrequency = floor(maxFrequency / 2) + 1
			count += 1
	print(count)
	t -= 1


from math import ceil, log2
from statistics import mode
t = int(input())
for j in range(t):
	a = int(input())
	b = list(map(int, input().split()))
	c = mode(b)
	print(ceil(log2(b.count(c))))


from collections import Counter
import math
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	c = Counter(A)
	k = max(c.values())
	print(math.ceil(math.log2(k)))


a = int(input())
for i in range(a):
	b = int(input())
	dist_a = {}
	list_a = list(map(int, input().split()))
	if b == len(set(list_a)):
		print(0)
	else:
		for j in range(b):
			if list_a[j] not in dist_a:
				dist_a[list_a[j]] = 1
			else:
				dist_a[list_a[j]] += 1
		max_count = max(dist_a.values())
		num = 0
		while max_count > 1:
			if max_count % 2 == 0:
				max_count = max_count // 2
				num += 1
			else:
				max_count = (max_count + 1) // 2
				num += 1
		print(num)


import math
from collections import Counter
test_case = int(input())
for _ in range(test_case):
	n = int(input())
	A = list(map(int, input().split()))
	freq = dict(Counter(A))
	m = max(list(freq.values()))
	print(math.ceil(math.log2(m)))


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for j in a:
		if j not in d:
			d[j] = 1
		else:
			d[j] += 1
	m = max(d.values())
	print(math.ceil(math.log(m, 2)))


from collections import Counter
import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = Counter(arr)
	l = list(x.values())
	y = max(l)
	print(math.ceil(math.log(y, 2)))


import math
for _ in range(int(input())):
	n = int(input())
	numbers = list(map(int, input().split()))
	count = {}
	for number in numbers:
		if number not in count:
			count[number] = 1
		else:
			count[number] += 1
	max_count = max(count.values())
	print(math.ceil(math.log(max_count, 2)))


import numpy as np

def get_minimum_operations(A):
	(unique, counts) = np.unique(A, return_counts=True)
	max_counts = max(counts)
	n = 0
	while max_counts > 1:
		max_counts = np.ceil(max_counts / 2)
		n += 1
	return n
T = int(input())
for _ in range(T):
	N = int(input())
	A = np.array(input().split(' ')).astype(int)
	print(get_minimum_operations(A))


from collections import defaultdict
T = int(input())
while T > 0:
	N = int(input())
	A = list(map(int, input().strip().split()))[:N]
	d = defaultdict(lambda : 0)
	for i in range(N):
		d[A[i]] += 1
	Max = 0
	for i in d:
		Max = max(Max, d[i])
	a = 0
	for i in range(33):
		if 2 ** i >= Max:
			a = i
			break
	print(a)
	T -= 1


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(el) for el in input().split(' ')]
	m = 0
	counts = {}
	for el in arr:
		if el in counts:
			counts[el] += 1
		else:
			counts[el] = 1
		if counts[el] > m:
			m = counts[el]
	res = 0
	while m > 1:
		res += 1
		m = m - m // 2
	print(res)


from collections import Counter
from math import floor
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = Counter(l)
	m = 0
	c = 0
	for i in d:
		if d[i] > m:
			m = d[i]
	while m > 1:
		if m % 2 == 0:
			m = floor(m / 2)
			c += 1
		else:
			m = floor(m / 2) + 1
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	if n <= 0:
		print(0)
	arr = list(map(int, input().split()))
	hashmap = {}
	for i in arr:
		if i in hashmap:
			hashmap[i] += 1
		else:
			hashmap[i] = 1
	maxi = 0
	for i in hashmap.values():
		if maxi < i:
			maxi = i
	ans = 0
	val = 1
	while val < maxi:
		ans += 1
		val *= 2
	print(ans)


def ans(arr):
	hm = {}
	for y in arr:
		if y in hm.keys():
			hm[y] += 1
		else:
			hm[y] = 1
	k = max(hm.values())
	count = 0
	while k > 1:
		if k % 2 == 0:
			k = k // 2
		else:
			k = (k + 1) // 2
		count += 1
	return count
test_cases = int(input())
while test_cases != 0:
	d = int(input())
	d2 = list(map(int, input().split()))
	print(ans(d2))
	test_cases -= 1


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = Counter(l)
	mx = max(d.values())
	ans = 0
	while mx > 1:
		if mx % 2 == 0:
			mx = mx // 2
		else:
			mx = mx // 2 + 1
		ans += 1
	print(ans)


import statistics
from statistics import mode
for g in range(int(input())):
	n = int(input())
	k = input().split(' ')
	c = k.count(mode(k))
	a = 0
	while c > 1:
		if c % 2 == 1:
			c = c // 2 + 1
		else:
			c = c // 2
		a += 1
	print(a)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = Counter(l)
	maxx = max(d.values())
	count = maxx
	ops = 0
	while count > 1:
		if count % 2 == 0:
			count /= 2
		else:
			count = (count + 1) // 2
		ops += 1
	print(ops)


import math
for _ in range(int(input())):
	k = int(input())
	a = list(map(int, input().split()))
	h = {}
	for i in a:
		if i in h:
			h[i] += 1
		else:
			h[i] = 1
	k = max(h.values())
	if k == 0:
		print(0)
	else:
		print(math.ceil(math.log(k, 2)))


for _ in range(int(input())):
	n = int(input())
	l = map(int, input().split())
	d = {}
	c = 0
	for i in l:
		if i not in d.keys():
			d[i] = 1
		else:
			d[i] = d[i] + 1
	ans = 0
	max_val = max(d.values())
	while max_val > 1:
		if max_val % 2 == 0:
			max_val = max_val // 2
		else:
			max_val = max_val // 2 + 1
		ans += 1
	print(ans)


from collections import Counter
from math import ceil, log
for i in range(int(input())):
	_ = input()
	arr = map(int, input().split())
	dct = Counter(arr)
	max_freq = max(dct.values())
	print(ceil(log(max_freq, 2)))


from collections import defaultdict
for _ in range(int(input())):
	length = int(input())
	arr = map(int, input().split())
	freq_arr = defaultdict(int)
	for elem in arr:
		freq_arr[elem] += 1
	maxitem_len = max(freq_arr.items(), key=lambda a: a[1])[1]
	(count, step) = (0, 1)
	while step < maxitem_len:
		count += 1
		step *= 2
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for j in a:
		if j not in d:
			d[j] = 1
		else:
			d[j] = d[j] + 1
	res = 0
	maxi = max(d.values())
	while maxi > 1:
		if maxi % 2 == 0:
			maxi = maxi / 2
		else:
			maxi = (maxi + 1) / 2
		res += 1
	print(res)


q = int(input())
for w in range(q):
	n = int(input())
	num = list(map(int, input().split()))
	dicts = {}
	for i in range(len(num)):
		if num[i] not in dicts:
			dicts[num[i]] = 1
		else:
			dicts[num[i]] += 1
	res = 0
	maxi = max(dicts.values())
	while maxi > 1:
		if maxi % 2 == 0:
			maxi = maxi // 2
		else:
			maxi = (maxi + 1) // 2
		res += 1
	print(res)


from typing import Counter
for i in range(int(input())):
	a = int(input())
	lst = map(int, input().split())
	x = dict(Counter(lst))
	maxm = 0
	for i in x.values():
		if i > maxm:
			maxm = i
	res = 0
	while maxm > 1:
		if maxm % 2 == 0:
			maxm //= 2
		else:
			maxm = (maxm + 1) // 2
		res += 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = {}
	for element in arr:
		if element not in count:
			count[element] = 1
		else:
			count[element] += 1
	max_frequency = max(count.values())
	cost = 0
	while max_frequency > 1:
		if max_frequency % 2 == 0:
			max_frequency = max_frequency / 2
		else:
			max_frequency = (max_frequency + 1) / 2
		cost += 1
	print(cost)


import statistics
from statistics import mode
for _ in range(int(input())):
	n = int(input())
	l = input().split(' ')
	count = l.count(mode(l))
	cost = 0
	while count > 1:
		if count % 2 == 1:
			count = count // 2 + 1
		else:
			count = count // 2
		cost += 1
	print(cost)


def fun(a, n):
	f = {}
	for i in range(n):
		if a[i] in f:
			f[a[i]] += 1
		else:
			f[a[i]] = 1
	k = 0
	h = max(f.values())
	while h > 1:
		if h % 2 == 0:
			h = h / 2
		else:
			h = (h + 1) / 2
		k += 1
	return k
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(fun(l, n))


import statistics
from statistics import mode

def rep(l):
	return mode(l)
n = int(input())
for i in range(n):
	q = int(input())
	l = list(map(int, input().split()))
	k = l.count(rep(l))
	s = 0
	while k != 1:
		s = s + 1
		if k % 2 == 0:
			k = k // 2
		else:
			k = k // 2 + 1
	print(s)


for t in range(int(input())):
	m = c = 0
	d = {}
	n = int(input())
	l = list(map(int, input().split()))
	for i in l:
		if i not in d.keys():
			d[i] = 1
		else:
			d[i] += 1
	for i in d.keys():
		if d[i] > m:
			m = d[i]
	while m > 1:
		if m % 2 == 0:
			m = m // 2
			c += 1
		else:
			m = m // 2 + 1
			c += 1
	print(c)


from math import ceil
testCaseLen = int(input())
for i in range(testCaseLen):
	n = int(input())
	arr = [int(val) for val in input(' ').split()]
	hashMap = {j: 0 for j in arr}
	for count in arr:
		hashMap[count] += 1
	high = max(hashMap.values())
	count = 0
	while high > 1:
		if high % 2 == 0:
			high = high // 2
		else:
			high = (high + 1) // 2
		count += 1
	print(count)


T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split(' ')]
	counts = {}
	notSames = False
	for a in A:
		if a not in counts:
			counts[a] = 0
		counts[a] += 1
		if notSames == False and counts[a] == 2:
			notSames = True
	if not notSames:
		print(0)
		continue
	mx = max(counts.values())
	ans = 0
	temp = 1
	while temp < mx:
		temp *= 2
		ans += 1
	print(ans)


def main():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	maxcnt = cnt = 1
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			cnt += 1
			if cnt > maxcnt:
				maxcnt = cnt
		else:
			cnt = 1
	if maxcnt < 4:
		print(maxcnt - 1)
		return
	maxcnt += maxcnt % 2
	ans = 1
	while 1:
		maxcnt = (maxcnt + 1) // 2 if maxcnt % 2 else maxcnt // 2
		if maxcnt < 2:
			break
		ans += 1
	print(ans)
for _ in range(int(input())):
	main()


def op():
	n = int(input())
	l = list(map(int, input().strip().split()))
	sorted(l)
	d = {}
	for x in l:
		if x in d.keys():
			d[x] += 1
		else:
			d[x] = 1
	m = max(d.values())
	count = 0
	while m > 1:
		if m % 2 == 0:
			m = m / 2
		else:
			m = (m + 1) / 2
		count += 1
	print(count)
t = int(input())
for i in range(t):
	op()