You are given an array $a$ of $n$ integers. Initially there is only one copy of the given array.

You can do operations of two types:

Choose any array and clone it. After that there is one more copy of the chosen array.

Swap two elements from any two copies (maybe in the same copy) on any positions.

You need to find the minimal number of operations needed to obtain a copy where all elements are equal.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case output a single integer — the minimal number of operations needed to create at least one copy where all elements are equal.


-----Examples-----

Input
6
1
1789
6
0 1 3 3 7 0
2
-1000000000 1000000000
4
4 3 2 1
5
2 5 7 6 3
7
1 1 1 1 1 1 1
Output
0
6
2
5
7
0


-----Note-----

In the first test case all elements in the array are already equal, that's why the answer is $0$.

In the second test case it is possible to create a copy of the given array. After that there will be two identical arrays:

$[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]$ and $[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]$

After that we can swap elements in a way so all zeroes are in one array:

$[ \ 0 \ \underline{0} \ \underline{0} \ 3 \ 7 \ 0 \ ]$ and $[ \ \underline{1} \ 1 \ 3 \ 3 \ 7 \ \underline{3} \ ]$

Now let's create a copy of the first array:

$[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$, $[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$ and $[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$

Let's swap elements in the first two copies:

$[ \ 0 \ 0 \ 0 \ \underline{0} \ \underline{0} \ 0 \ ]$, $[ \ \underline{3} \ \underline{7} \ 0 \ 3 \ 7 \ 0 \ ]$ and $[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$.

Finally, we made a copy where all elements are equal and made $6$ operations.

It can be proven that no fewer operations are enough.

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Sorting

Constructive algorithms


Solutions:
from collections import Counter
for li in [*open(0)][2::2]:
	n = len((li := li.split()))
	m = max(Counter(li).values())
	ans = n - m
	while m < n:
		ans += 1
		m = 2 * m
	print(ans)


from collections import *
for a in [*open(0)][2::2]:
	n = len((a := a.split()))
	m = max(Counter(a).values())
	r = n - m
	while m < n:
		r += 1
		m *= 2
	print(r)


from sys import stdin
from collections import defaultdict

def main():
	sr = stdin.readline
	t = int(sr())
	for _ in range(t):
		n = int(sr())
		l = list(map(int, sr().split()))
		c = defaultdict(int)
		for num in l:
			c[num] += 1
		v = max(c.values())
		ret = n - v
		while v < n:
			v <<= 1
			ret += 1
		print(ret)
main()


from collections import Counter
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	w = input().split()
	s = max(Counter(w).values())
	a = n - s
	while s < n:
		a += 1
		s *= 2
	print(a)


from collections import *
for i in [*open(0)][2::2]:
	a = len((i := i.split()))
	b = max(Counter(i).values())
	s = a - b
	while a > b:
		s += 1
		b *= 2
	print(s)


import sys
t = int(sys.stdin.readline())
for _ in range(0, t):
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().strip().split()))
	b = dict()
	for i in arr:
		if i in b:
			b[i] += 1
		else:
			b[i] = 1
	c = b[max(b, key=b.get)]
	count = 0
	if n == 1:
		count = 0
	else:
		while c <= n:
			if c == n:
				break
			if 2 * c <= n:
				count = count + c + 1
				c = 2 * c
			elif 2 * c > n:
				count = count + c - (2 * c - n) + 1
				c = c + (c - (2 * c - n))
	print(count)


import sys
input = sys.stdin.readline
for iiiabcd in range(int(input())):
	n = int(input())
	d = {}
	ans = 0
	for i in map(int, input().split()):
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	s = max(d.values())
	while s < n:
		if s <= int(n / 2):
			ans += 1 + s
		else:
			ans += 1 + n - s
		s += s
	print(ans)


from collections import Counter
for a in [*open(0)][2::2]:
	n = len((a := a.split()))
	b = max(Counter(a).values())
	cnt = n - b
	while b < n:
		b *= 2
		cnt += 1
	res = cnt
	print(res)


import sys

def nextline():
	return sys.stdin.readline().rstrip('\r\n')

def min_number_of_doublings(max_occ, array_len):
	min_num = 0
	while max_occ < array_len:
		min_num += 1
		max_occ *= 2
	return min_num
test_cases = int(nextline())
for i in range(test_cases):
	array_len = int(nextline())
	array = nextline().split()
	element_frequencies = dict()
	for i in range(len(array)):
		element_frequencies[array[i]] = element_frequencies.get(array[i], 0) + 1
	max_occurrence = 0
	for key in element_frequencies.keys():
		if element_frequencies[key] > max_occurrence:
			max_occurrence = element_frequencies[key]
	print(min_number_of_doublings(max_occurrence, array_len) + array_len - max_occurrence)


def solve():
	d = {}
	for i in arr:
		d[i] = d.get(i, 0) + 1
	mx = 0
	for i in d:
		mx = max(mx, d[i])
	for i in d:
		if d[i] == mx:
			key = i
			break
	ans = n - d[key]
	if ans == 0:
		return 0
	while d[key] < n:
		ans += 1
		d[key] *= 2
	return ans
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve())


import sys
number_of_data = int(sys.stdin.readline())
for i in range(number_of_data):
	n = int(sys.stdin.readline())
	my_list = sys.stdin.readline().split()
	my_list = [int(x) for x in my_list]
	my_list.sort()
	max_count = 1
	max_now = 1
	for j in range(n - 1):
		if my_list[j + 1] == my_list[j]:
			max_now += 1
			if max_count < max_now:
				max_count = max_now
		else:
			if max_count < max_now:
				max_count = max_now
			max_now = 1
	k = 0
	while 2 ** k * max_count < n:
		k += 1
	print(k + n - max_count)


import sys, math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	nums = inlt()
	d = {}
	for num in nums:
		d[num] = d.get(num, 0) + 1
	y = max(d.values())
	print(n - y + math.ceil(math.log2(math.ceil(n / y))))


def q(n, s):
	s.sort()
	qw = 1
	m = 1
	for i in range(n - 1):
		if s[i] < s[i + 1]:
			if qw < m:
				qw = m
			m = 1
		else:
			m += 1
	qw = max(m, qw)
	w = 0
	g = n - qw
	while g > 0:
		w += 1 + min(qw, g)
		g -= min(qw, g)
		qw *= 2
	return w
n = int(input())
w = []
for i in range(n):
	a = int(input())
	s = list(map(int, input().split()))
	w.append(q(a, s))
for i in range(n):
	print(w[i])


from sys import stdin
t = int(stdin.readline())
while t > 0:
	t -= 1
	n = int(stdin.readline())
	a = sorted(list(map(int, stdin.readline().split())))
	M = 1
	temp = 1
	for i in range(1, n):
		if a[i] > a[i - 1]:
			temp = 1
		else:
			temp += 1
		M = max(M, temp)
	ind = 0
	temp = M
	while temp < n:
		ind += 1
		temp *= 2
	print(n - M + ind)


from collections import Counter

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		print(solve(n, arr))

def solve(n, arr):
	k = Counter(arr).most_common(1)[0][1]
	count = 0
	m = k
	while m < n:
		count += 1
		moved = min(n - m, m)
		m += moved
		count += moved
	return count
import sys
input = sys.stdin.readline
exit(main())


from itertools import groupby
from math import ceil, log2
from sys import stdin, stdout
read = stdin.readline
write = stdout.write
for _ in range(int(read())):
	n = int(read())
	arr = sorted(list(map(int, read().split())))
	freq = [(len(list(k)), g) for (g, k) in groupby(arr)]
	freq.sort(reverse=True)
	try:
		print(ceil(log2(n / freq[0][0])) + n - freq[0][0])
	except:
		print(0)


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		A = list(input().split())
		counter = dict()
		max_count = 0
		for k in A:
			if k not in counter:
				counter[k] = 0
			counter[k] += 1
			if counter[k] > max_count:
				max_count = counter[k]
		swap_count = n - max_count
		copy_count = 0
		a = max_count
		while a < n:
			a = a * 2
			copy_count += 1
		print(swap_count + copy_count)
main()


import collections
import sys
input = sys.stdin.readline
for k in range(int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	m = max(collections.Counter(v).values())
	if n == m:
		print(0)
	else:
		s = 0
		res = 0
		while m * 2 ** (s + 1) < n:
			s += 1
		res = 0
		for j in range(s):
			res += 1
			res += m * 2 ** j
		res += n - m * 2 ** s
		print(res + 1)


import sys
import math
input = sys.stdin.readline
from collections import Counter
import statistics
from statistics import mode

def max_dup(a, n):
	a.sort()
	cnt = 1
	mx = 0
	for i in range(1, n):
		if a[i] == a[i - 1]:
			cnt += 1
		else:
			mx = max(mx, cnt)
			cnt = 1
	mx = max(mx, cnt)
	return mx
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	max_dupl = max_dup(a, n)
	step = n - max_dupl
	if n / max_dupl == 2:
		step += 1
	else:
		step += math.ceil(math.log(n, 2) - math.log(max_dupl, 2))
	print(step)


import sys
from collections import *

def prin(a):
	sys.stdout.write(str(a) + '\n')

def input():
	return sys.stdin.readline().strip()
mod = int(1000000000.0 + 7)
x8 = [-1, -1, 0, 1, 1, 1, 0, -1]
y8 = [0, 1, 1, 1, 0, -1, -1, -1]
for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	d = {}
	q = w = -1000000000.0
	for i in l:
		d.setdefault(i, 0)
		d[i] += 1
	for i in d:
		if d[i] <= w:
			continue
		q = i
		w = d[i]
	r = n - w
	ct = 0
	while r:
		ct += 1
		if w < r:
			r -= w
			ct += w
			w *= 2
		else:
			ct += r
			break
	print(ct)


def ans(ar, n):
	dict = {}
	for i in ar:
		if i not in dict:
			dict[i] = 1
		else:
			dict[i] += 1
	ls = []
	for i in dict:
		ls.append(dict[i])
	ls.sort()
	max = ls[-1]
	ans = max
	count = 0
	while max < n:
		max *= 2
		count += 1
	print(n + count - ans)

def solve():
	n = int(input())
	ar = input().split(' ')
	ans(ar, n)
t = int(input())
for i in range(t):
	solve()


import math
import sys
from collections import deque
import heapq
from collections import Counter

def inp():
	return sys.stdin.readline().rstrip()

def mpp():
	return map(int, inp().split())

def lis():
	return list(mpp())

def sol(arr, n):
	di = Counter(arr)
	key = 0
	for i in di:
		key = max(key, di[i])
	count = n - key
	sum = key
	while sum < n:
		count += 1
		sum = sum * 2
	return count

def main():
	t = int(inp())
	for _ in range(t):
		n = int(inp())
		arr = lis()
		print(sol(arr, n))
main()


from collections import Counter
for i in range(int(input())):
	n = int(input())
	t_max = max(Counter(input().split()).values())
	cnt = 0
	probe = t_max
	while probe < n:
		probe *= 2
		cnt += 1
	res = n - t_max + cnt
	print(res)


for t in range(int(input())):
	n = int(input())
	c = {}
	for i in input().split():
		if c.get(i, 0):
			c[i] += 1
		else:
			c[i] = 1
	m = max(c.values())
	c = n - m
	while m < n:
		c += 1
		m *= 2
	print(c)


import sys
import math
input = sys.stdin.readline
from collections import Counter
import statistics
from statistics import mode

def max_dup(List):
	dict = {}
	(count, itm) = (0, '')
	for item in reversed(List):
		dict[item] = dict.get(item, 0) + 1
		if dict[item] >= count:
			(count, itm) = (dict[item], item)
	return itm
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	max_dupl = a.count(max_dup(a))
	step = n - max_dupl
	if n / max_dupl == 2:
		step += 1
	else:
		step += math.ceil(math.log(n, 2) - math.log(max_dupl, 2))
	print(step)


for _ in range(int(input())):
	n = int(input())
	dic = {}
	for i in input().split():
		if dic.get(i, 0):
			dic[i] += 1
		else:
			dic[i] = 1
	most = max(dic.values())
	copies = n - most
	while most < n:
		copies += 1
		most *= 2
	print(copies)


def solve(n, max_num):
	left_num = n - max_num
	base = 1
	i = 0
	for i in range(1, 35):
		if base * max_num >= left_num:
			return i
		left_num = left_num - base * max_num
		base = base * 2
	return i
N = int(input())
for _ in range(N):
	n = int(input())
	list_num = input().split(' ')
	if n == 1:
		print('0')
		continue
	d = dict()
	for num in list_num:
		if num in d:
			d[num] = d[num] + 1
		else:
			d[num] = 1
	max_num = max(d.values())
	if n == max_num:
		print('0')
		continue
	time = solve(n, max_num)
	ans = n - max_num + time
	print(ans)


for _ in range(int(input())):
	n = int(input())
	numbers = list(map(int, input().split(' ')))
	len_nb = len(numbers)
	nb_dict = dict()
	for nb in numbers:
		if nb in nb_dict:
			nb_dict[nb] += 1
		else:
			nb_dict[nb] = 1
	max_val = max(nb_dict.values())
	ans = n - max_val
	while max_val < n:
		ans += 1
		max_val *= 2
	print(ans)


from collections import Counter

def solve():
	n = int(input())
	freq = max(Counter(input().split()).values())
	left = n - freq
	ans = 0
	while left:
		ans += 1 + min(left, freq)
		left = left - min(left, freq)
		freq = 2 * freq
	print(ans)
while True:
	try:
		test = int(input())
	except EOFError:
		break
	for i in range(test):
		solve()


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	m = max(Counter(input().split()).values())
	ans = n - m
	while m < n:
		ans += 1
		m *= 2
	print(ans)


from collections import Counter
for t in range(int(input())):
	n = int(input())
	m = max(Counter(input().split()).values())
	c = n - m
	while m < n:
		c += 1
		m *= 2
	print(c)


import sys
from collections import Counter
inp = sys.stdin.readline()
test = int(inp.strip('\n'))
result = ''
for i in range(test):
	inp = sys.stdin.readline()
	n = int(inp.strip('\n'))
	inp = sys.stdin.readline()
	l = list(map(int, inp.strip('\n').split()))
	counted = Counter(l)
	steps = 0
	high = max(counted.values())
	while True:
		if high == n:
			break
		steps += 1
		if high <= n // 2:
			steps += high
			high <<= 1
		else:
			steps += n - high
			high = n
	sys.stdout.write(str(steps) + '\n')


from collections import Counter

def calculate(arr):
	(elem, count) = Counter(arr).most_common(1)[0]
	swaps = len(arr) - count
	copies = 0
	while True:
		if count >= len(arr):
			print(swaps + copies)
			return
		count *= 2
		copies += 1
cases = int(input())
for i in range(cases):
	input()
	calculate(input().split(' '))


t = int(input())
res = []
for _ in range(t):
	input()
	a = [int(x) for x in input().split(' ')]
	d = {}
	for v in a:
		if v in d:
			d[v] += 1
		else:
			d[v] = 1
	mx = float('-inf')
	for k in d:
		mx = max(mx, d[k])
	(needed, ans) = (len(a) - mx, 0)
	while needed:
		tf = min(mx, needed)
		ans += tf + 1
		mx += tf
		needed -= tf
	res.append(ans)
for i in range(t):
	print(res[i])


t = int(input())
for i in range(t):
	n = int(input())
	duplicates = {}
	a = input().split()
	for j in range(n):
		if a[j] not in duplicates:
			duplicates[a[j]] = 1
		else:
			duplicates[a[j]] += 1
	count = 0
	if len(duplicates) > 1:
		mx = max(duplicates.values())
		while mx * 2 < n:
			count += 1 + mx
			mx *= 2
		count += n - mx + 1
	print(int(count))


x = int(input())
from collections import Counter
for i in range(x):
	a = int(input().strip())
	b = max(Counter(map(int, input().split())).values())
	sum1 = a - b
	while a > b:
		b *= 2
		sum1 += 1
	print(sum1)


def main():
	n = int(input())
	array = [s for s in input().split(' ')]
	freq = {}
	for x in array:
		if x in freq:
			freq[x] += 1
		else:
			freq[x] = 1
	target = max(freq, key=freq.get)
	target_freq = freq[target]
	operations = 0
	remaining_count = len(array) - target_freq
	while target_freq < len(array):
		swapped = min(target_freq, remaining_count)
		target_freq += swapped
		remaining_count -= swapped
		operations += swapped + 1
	return operations
T = int(input())
for t in range(1, T + 1):
	print(main())


from collections import Counter
import math

def fun(ans):
	l = len(ans)
	if l == 1:
		return 0
	d = Counter(ans)
	m = 0
	mc = -1
	for i in d:
		if d[i] > m:
			m = d[i]
	x = l - m
	c = x
	while x > 0:
		x -= m
		m *= 2
		c += 1
	return c
n = int(input())
for _ in range(n):
	_ = input()
	arr = input().split()
	print(fun(arr))


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	d = dict()
	for x in arr:
		if x in d:
			d[x] += 1
		else:
			d[x] = 1
	mx = 0
	for x in arr:
		if d[x] > mx:
			mx = d[x]
	ans = 0
	while True:
		if mx < n:
			if mx + mx <= n:
				ans += mx
				mx = mx + mx
			else:
				ans += n - mx
				mx = n
			ans += 1
		else:
			break
	print(ans)
t = int(input())
for i in range(t):
	solve()


T = int(input())
for j in range(T):
	tmp1 = input()
	goal_array = list(map(int, input().split(' ')))
	goal_array.sort()
	elements = len(goal_array)
	tmp = 1
	max_answer = 1
	for i in range(1, len(goal_array)):
		if goal_array[i] == goal_array[i - 1]:
			tmp = tmp + 1
		else:
			if tmp > max_answer:
				max_answer = tmp
			tmp = 1
	if tmp > max_answer:
		max_answer = tmp
	extra_number = max_answer
	for k in range(100):
		if extra_number >= elements:
			print(k + elements - max_answer)
			break
		else:
			extra_number = extra_number * 2


import math
t = int(input())
for xx in range(t):
	n = int(input())
	b = input().split()
	a = [int(j) for j in b]
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	mz = 0
	for (i, j) in d.items():
		if j > mz:
			mz = j
	c = 0
	while mz < n:
		c += 1 + min(mz, n - mz)
		mz *= 2
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	q = {}
	for i in a:
		q[i] = q.get(i, 0) + 1
	w = max(q.values())
	ans = n - w
	while w < n:
		ans += 1
		w *= 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dict = {}
	for i in a:
		if i not in dict:
			dict[i] = 1
		else:
			dict[i] += 1
	p = max(dict.values())
	t = n - p
	count = 0
	while t > 0:
		if t >= p:
			t -= p
			count += p + 1
		else:
			count += t + 1
			t = 0
			break
		p *= 2
	print(count)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(int)
	for a in map(int, input().split()):
		d[a] += 1
	m = max(d.values())
	c = n - m
	while m < n:
		c += 1
		m <<= 1
	print(c)


def solve(n, l):
	if n == 1:
		print(0)
	else:
		d = {}
		ma = 0
		for i in l:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
			ma = max(ma, d[i])
		c = 0
		n -= ma
		if n == 0:
			print(0)
		else:
			while n - ma >= 0:
				n -= ma
				c += ma + 1
				ma = 2 * ma
			if n > 0:
				c += n + 1
			print(c)
t = int(input())
for test in range(t):
	num = int(input())
	lst = list(map(int, input().split()))
	solve(num, lst)


import sys
import math
from sys import stdin, stdout

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

def get_int():
	return int(input())

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

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def main():
	for t in range(get_int()):
		n = int(input())
		arr = get_ints_in_list()
		mp = {}
		for i in range(0, n):
			if arr[i] not in mp:
				mp[arr[i]] = 1
			else:
				mp[arr[i]] += 1
		mx = 0
		for (key, val) in mp.items():
			if val > mx:
				mx = val
		change = n - mx
		if change == 0:
			print(0)
		else:
			res = 0
			while change != 0 and mx != n:
				res += 1
				tmp = mx
				res += min(change, tmp)
				change -= min(change, tmp)
				mx += tmp
			print(res)
main()


import math
t = int(input())
res = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	(m, j) = (0, 0)
	for x in a:
		d[x] = d[x] + 1 if d.get(x) else 1
		if d[x] > m:
			(m, j) = (d[x], x)
	r = 0
	raz = len(a) - m
	r += raz
	r += int(math.ceil(math.log2(1 + raz / m)))
	res.append(r)
for el in res:
	print(el)


t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = len(set(a))
	a.sort()
	x = 1
	y = 1
	for r in range(1, n):
		if a[r - 1] == a[r]:
			x += 1
		else:
			if x > y:
				y = x
			x = 1
	if x > y:
		y = x
	ans = 0
	while y < n:
		if 2 * y < n:
			ans += y + 1
			y *= 2
		else:
			ans += n - y + 1
			y = n
	print(ans)


import sys
import math
import itertools
mod = 998244353

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def rls():
	return list(map(str, input().split()))

def rm():
	return map(int, input().split())

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def nextPowerOf2(n):
	n -= 1
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n += 1
	return n

def highestPowerof2(x):
	x |= x >> 1
	x |= x >> 2
	x |= x >> 4
	x |= x >> 8
	x |= x >> 16
	return x ^ x >> 1
for _ in range(ri()):
	n = ri()
	a = rl()
	if n == 1:
		print(0)
		continue
	d = {}
	for i in a:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	m = max(d.values())
	i = 2 * m
	ans = 1
	if a.count(a[0]) == n:
		ans = 0
	while i < n:
		ans += 1
		i = i * 2
	print(ans + n - m)


from sys import stdin, stdout
from collections import Counter, defaultdict
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	if min(arr) == max(arr):
		print(0)
		continue
	d = Counter(arr)
	maxi = 0
	for key in d:
		maxi = max(maxi, d[key])
	k = 2 * maxi
	cnt1 = 0
	cnt2 = 0
	while k < n:
		cnt1 += 1
		cnt2 += k // 2
		k = k * 2
	if k >= n:
		cnt2 += n - k // 2 + 1
	print(cnt1 + cnt2)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	min1 = 0
	s = 0
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	for i in d:
		if d[i] > min1:
			min1 = d[i]
			m = i
	s = n - d[m]
	c2 = s
	while d[m] < n:
		s += 1
		d[m] *= 2
	print(s)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	dict = {}
	(count, itm) = (0, '')
	for item in a:
		dict[item] = dict.get(item, 0) + 1
	count = max(dict.values())
	ans = n - count
	while count < n:
		ans += 1
		count *= 2
	print(ans)


N = int(input())
for _ in range(N):
	n = int(input())
	list_num = input().split(' ')
	d = dict()
	for num in list_num:
		if num in d:
			d[num] = d[num] + 1
		else:
			d[num] = 1
	max_num = max(d.values())
	now = max_num
	ans = 0
	copy = 0
	while now < n:
		if copy > 0:
			ans += 1
			copy -= 1
			now += 1
		else:
			ans += 1
			copy = now
	print(ans)


from collections import Counter
testcases = input()

def solve():
	n = int(input().strip())
	c = Counter(map(int, input().strip().split(' ')))
	max_rep = max(c.values())
	swap_op = n - max_rep
	copy_op = 0
	ans = swap_op
	while swap_op > 0:
		swap_op -= max_rep
		max_rep *= 2
		ans += 1
	return ans
for caseNr in range(1, int(testcases) + 1):
	print('%s' % solve())


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	C = Counter(A)
	maxnum = max(C.values())
	if maxnum == n:
		print(0)
		continue
	ope = n - maxnum
	while maxnum < n:
		ope += 1
		maxnum *= 2
	print(ope)


def func(n, k):
	if n == k:
		return 0
	i = n - k
	if i <= k:
		return 1 + i
	else:
		return 1 + k + func(n, 2 * k)

def mf(a):
	p = len(a)
	d = {}
	for i in a:
		d[i] = 0
	for i in a:
		d[i] += 1
	max = 0
	for i in a:
		if d[i] > max:
			max = d[i]
	return max
t = int(input())
for i in range(t):
	n = int(input())
	l = input().split(' ')
	l = [int(i) for i in l]
	k = mf(l)
	out = func(n, k)
	print(out)


from collections import *
for i in range(int(input())):
	a = int(input())
	b = max(Counter(input().split()).values())
	s = a - b
	while a > b:
		s += 1
		b *= 2
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if len(set(a)) == 1:
		print(0)
		continue
	d = dict()
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	s = 0
	c = max(d.values())
	k = 0
	while c < n:
		k += 1
		c = c * 2
	print(n - max(d.values()) + k)


t = int(input())
for qwer in range(t):
	n = int(input())
	sp = list(map(int, input().split()))
	d = dict()
	m = 0
	for el in sp:
		if el not in d:
			d[el] = 1
		else:
			d[el] += 1
	m = max(d.values())
	ans = 0
	r = n - m
	colvo = 0
	sm = 0
	k = 1
	while sm < r:
		colvo += 1
		k *= 2
		sm = m * (k - 1)
	print(colvo + r)


from collections import Counter
t = int(input())
for qwer in range(t):
	n = int(input())
	sp = list(map(int, input().split()))
	m = 0
	d = Counter(sp)
	m = max(d.values())
	ans = 0
	r = n - m
	colvo = 0
	sm = 0
	k = 1
	while sm < r:
		colvo += 1
		k *= 2
		sm = m * (k - 1)
	print(colvo + r)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = {x: 0 for x in a}
	for item in a:
		count[item] += 1
	count = list(count.values())
	chose = max(count)
	others = sum(count) - chose
	operations = 0
	while others > 0:
		operations += 1
		if chose > others:
			operations += others
			break
		else:
			others -= chose
			operations += chose
			chose *= 2
	print(operations)


import math
for t in range(int(input())):
	n = int(input())
	L = input().split()
	count = {}
	for i in L:
		try:
			count[i] += 1
		except:
			count[i] = 1
	m = max(list(count.values()))
	print(int(n - m + math.ceil(math.log(n / m, 2))))


from collections import Counter
t = int(input())
result = []
for _ in range(t):
	n = int(input())
	array = input().split()
	currentMax = max(Counter(array).values())
	currentElems = currentMax
	count = 0
	while currentElems < n:
		diff = min(n - currentElems, currentElems)
		count += 1 + diff
		currentElems += diff
	ans = count
	print(ans)


for t in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr1.sort()
	c = arr1[0]
	cc = 1
	mx = 1
	for i in range(1, n):
		if arr1[i] == c:
			cc += 1
		else:
			c = arr1[i]
			if mx < cc:
				mx = cc
			cc = 1
	if mx < cc:
		mx = cc
	cc = 0
	if mx == n:
		print(0)
	else:
		z = mx
		while mx < n:
			cc += 1
			mx *= 2
		print(n - z + cc)


def mostFrequent(arr, n):
	arr.sort()
	max_count = 1
	res = arr[0]
	curr_count = 1
	for i in range(1, n):
		if arr[i] == arr[i - 1]:
			curr_count += 1
		else:
			curr_count = 1
		if curr_count > max_count:
			max_count = curr_count
			res = arr[i - 1]
	return max_count
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	c = mostFrequent(arr, n)
	step = 0
	while c < n:
		d = min(c, n - c)
		step += 1 + d
		c += d
	print(step)


import sys

def solve():
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	d = dict()
	for i in a:
		d[i] = d.get(i, 0) + 1
	now = 0
	for i in d:
		now = max(now, d[i])
	r = 0
	while now < n:
		w = min(now, n - now)
		now += w
		r += 1 + w
	print(r)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()