Read problems statements in Mandarin Chinese  and Russian. 

Chef has a box full of infinite number of identical coins. One day while playing, he made N piles each containing equal number of coins. Chef suddenly remembered an important task and left the room for sometime. While he was away, his newly hired assistant came across the piles and mixed them up while playing.
When Chef returned home, he was angry to see that all of his piles didn't contain equal number of coins as he very strongly believes in the policy of equality for all, may it be people or piles of coins. 

In order to calm down the Chef, the assistant proposes to make all the piles equal. Chef agrees to give this task to him, but as a punishment gives him only two type of operations that he can perform.

Pick some coins from any pile and put them back in Chef's coin box.
Pick some coins from the Chef's coin box and put them on any one pile.
  
The assistant wants to do this task as fast as possible. So he wants to know the minimum number of operations needed to make all the piles equal.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases.		
The first line of each test case contains a single integer N denoting the number of piles.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the number of coins in each pile.
 
------ Output ------ 

For each test case, output a single line containing an integer corresponding to the minimum number of operations assistant needs to do.

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

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{5}$

------ Sub tasks ------ 

$Subtask #1: 1 ≤ N ≤ 1000 (30 points)$
$Subtask #2: original constraints (70 points)$

----- Sample Input 1 ------ 
1

4

1 2 3 4
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 

In test case 1, if you decide to convert all the piles to contain either of 1, 2, 3, or 4 coins you will have to change the other 3 piles. For any other choice you will have to alter more than 3 (i.e. 4) piles.

Difficulty: EASY
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	d = {}
	for i in lst:
		if i not in d.keys():
			d[i] = 1
		else:
			d[i] += 1
	print(n - max(d.values()))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = Counter(a)
	d = max(d.values())
	print(n - d)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	Dict = {}
	for j in a:
		if j in Dict:
			Dict[j] += 1
		else:
			Dict[j] = 1
	max_a = -1
	for (key, value) in Dict.items():
		if max_a < value:
			max_a = value
	print(len(a) - max_a)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	x = list(set(l))
	for i in x:
		d[i] = 0
	for i in l:
		d[i] += 1
	max = None
	for coin in d:
		if max is None:
			max = d[coin]
		elif d[coin] > max:
			max = d[coin]
	print(n - max)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	m1 = 0
	for i in d.values():
		m1 = max(m1, i)
	print(n - m1)


T = int(input())
for t in range(T):
	N = int(input())
	countd = dict()
	data = list(map(int, input().split()))
	for d in data:
		if d in countd:
			countd[d] += 1
		else:
			countd[d] = 1
	print(len(data) - max(countd.values()))


for _ in range(int(input())):
	n = int(input())
	arr = [int(j) for j in input().split()]
	mp = {}
	for i in range(n):
		if arr[i] not in mp:
			mp[arr[i]] = 1
		else:
			mp[arr[i]] += 1
	res = []
	for val in mp.values():
		res.append(val)
	print(n - max(res))


from collections import Counter
for i in range(int(input())):
	N = int(input())
	A = [int(k) for k in input().split()]
	A = Counter(A)
	del A[A.most_common(1)[0][0]]
	add = sum(A.values())
	print(add)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	d1 = {}
	for i in arr:
		if d1.get(i) is None:
			d1[i] = 1
		else:
			d1[i] += 1
	print(n - max(d1.values()))


from collections import Counter
t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	print(n - max(Counter(a).values()))


tt = int(input())
for i in range(tt):
	n = int(input())
	arr = list(map(int, input().split()))
	freq = [0] * int(100000.0 + 1)
	for i in arr:
		freq[i] += 1
	print(n - max(freq))


import collections
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	co = collections.Counter(arr)
	mx = max(co.values())
	print(n - mx)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mp = {}
	res = 0
	for i in a:
		if i not in mp:
			mp[i] = 1
		else:
			mp[i] += 1
	for i in mp.values():
		res = max(res, i)
	print(n - res)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	dt = {}
	for num in a:
		dt[num] = dt.get(num, 0) + 1
	print(n - max(list(dt.values())))


import statistics
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	temp = statistics.mode(arr)
	c = 0
	for i in arr:
		if i == temp:
			c += 1
	print(n - c)


t = int(input())
for _ in range(t):
	n = int(input())
	listi = sorted(list(map(int, input().split())))
	count_max = 0
	count = 0
	for i in range(len(listi)):
		for j in range(i, len(listi)):
			if listi[i] == listi[j]:
				count = count + 1
			else:
				break
		if count > count_max:
			count_max = count
			i = i + count - 1
			count = 0
		else:
			i = i + count - 1
			count = 0
	print(n - count_max)
	count = 0
	count_max = 0


for testcases in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if l[i] in d:
			d[l[i]] += 1
		else:
			d[l[i]] = 1
	print(n - max(d.values()))


from statistics import mode
t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	m = mode(A)
	ans = 0
	for i in A:
		if i == m:
			ans += 1
	print(N - ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = 1
	f = {}
	for i in a:
		if i in f:
			f[i] += 1
			if m < f[i]:
				m = f[i]
		else:
			f[i] = 1
	print(n - m)


from collections import Counter
testcase = int(input())
for i in range(testcase):
	n = int(input())
	l = list(map(int, input().split()))
	k = list(dict(Counter(l)).values())
	print(n - max(k))


t = int(input())
for i in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	d = {}
	for i in li:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	k = d.keys()
	f = list(d.values())
	h = max(f)
	l = len(li)
	print(l - h)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for j in a:
		if j in d:
			d[j] += 1
		else:
			d[j] = 1
	maxD = max(d.values())
	print(n - maxD)


n = int(input())
for i in range(n):
	x = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	a = list(d.values())
	b = max(a)
	print(x - b)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	freq = []
	for i in range(n):
		if l[i] not in d:
			d[l[i]] = 1
		else:
			d[l[i]] += 1
	for i in d:
		freq.append(d[i])
	print(n - max(freq))


t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	d = {}
	for i in A:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	print(n - max(d.values()))


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = {}
	count = 0
	for i in a:
		if c.get(i) is None:
			c[i] = 1
		else:
			c[i] += 1
	print(n - max(c.values()))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = list(dict(Counter(a)).values())
	print(n - max(l))


for _ in range(int(input())):
	n = int(input())
	arr_no_of_coins = list(map(int, input().split()))
	max_change_required = n
	d = {}
	for i in arr_no_of_coins:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	max_same = 0
	for i in d:
		if d[i] > max_same:
			max_same = d[i]
	print(n - max_same)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	x = max(d, key=d.get)
	print(len(a) - d[x])


from collections import Counter
for i in range(int(input())):
	N = int(input())
	A = [int(k) for k in input().split()]
	A = Counter(A)
	mst = dict(A.most_common())
	del mst[next(iter(mst))]
	add = sum(mst.values())
	print(add)


n = int(input())
for i in range(n):
	t = int(input())
	lst = [int(i) for i in input().split(' ')][:t]
	d = {}
	for i in lst:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	m = max(d.values())
	print(t - m)


from collections import Counter
for x in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = list(dict(Counter(l)).values())
	print(n - max(c))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	x = {}
	for i in range(len(a)):
		if a[i] in x:
			x[a[i]] += 1
		else:
			x[a[i]] = 1
	maxx = -9999
	for (i, j) in x.items():
		if j > maxx:
			maxx = j
	print(n - maxx)


import statistics
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(d, c) = ({}, 0)
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	temp = max(d, key=lambda x: d[x])
	for i in arr:
		if i == temp:
			c += 1
	print(n - c)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	m = max(d.values())
	c = 0
	for v in d.values():
		c += v
	print(c - m)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	m = max(c.values())
	print(n - m)


t = int(input())
for i in range(t):
	n = int(input())
	coin = list(map(int, input().split()))
	dict_Coin = dict()
	for ele in coin:
		if ele in dict_Coin:
			dict_Coin[ele] += 1
		else:
			dict_Coin[ele] = 1
	max = 0
	for key in dict_Coin:
		if dict_Coin[key] > max:
			max = dict_Coin[key]
			pos = key
	sum = 0
	for key in dict_Coin:
		if key != pos:
			sum += dict_Coin[key]
	print(sum)


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


T = int(input())
for i in range(0, T):
	a = int(input())
	b = input().split()
	aa = 0
	ab = {}
	for j in b:
		ab[j] = 0
	for j in b:
		ab[j] += 1
	for j in b:
		aa = max(ab[j], aa)
	print(a - aa)


for _ in range(int(input())):
	n = int(input())
	lst = [int(x) for x in input().split()]
	d = {}
	for i in lst:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	l = list(d.values())
	print(n - max(l))


import statistics
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = statistics.mode(a)
	c = 0
	for i in a:
		if i == m:
			c += 1
	print(n - c)


def main():
	testcases = int(input())
	i = 0
	while i < testcases:
		N = int(input())
		coins = input().split()
		for j in range(len(coins)):
			coins[j] = int(coins[j])
		dic = make_zero(coins)
		for coin in coins:
			dic[coin] += 1
		max = None
		for coin in dic:
			if max is None:
				max = dic[coin]
			elif dic[coin] > max:
				max = dic[coin]
		print(N - max)
		i += 1

def make_zero(coins):
	dic = {}
	for coin in coins:
		dic[coin] = 0
	return dic
main()


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))[:n]
	dic = dict()
	for i in lst:
		if i not in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	big = max(list(dic.values()))
	print(n - big)


for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split(' ')))
	d = {}
	for i in li:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	print(len(li) - max(d.values()))


for _ in range(int(input().strip())):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	hash = {}
	for m in a:
		hash[m] = hash.get(m, 0) + 1
	s = []
	for m in hash.keys():
		s.append((hash[m], m))
	s.sort(reverse=True)
	k = s[0][0]
	print(n - k)


from collections import Counter
for x in range(int(input())):
	n = int(input())
	a = [int(d) for d in input().split()]
	d = dict(Counter(a))
	m = max(list(d.values()))
	print(n - m)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	sets = {}
	for i in arr:
		if i not in sets:
			sets[i] = 1
		else:
			sets[i] += 1
	print(len(arr) - max(sets.values()))


from statistics import mode
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = mode(a)
	count = a.count(m)
	print(len(a) - count)


for _ in range(int(input())):
	l = int(input())
	arr = list(map(int, input().split()))
	dict = {}
	for a in arr:
		if a in dict:
			dict[a] += 1
		else:
			dict[a] = 1
	print(len(arr) - max(dict.values()))


test = int(input())
for i in range(test):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * (10 ** 5 + 1)
	for i in range(n):
		num = a[i]
		b[num] += 1
	maxi = max(b)
	print(n - maxi)


n = int(input())
for i in range(n):
	m = int(input())
	lis = list(map(int, input().split()))
	d = {}
	for i in lis:
		if i not in d.keys():
			d[i] = 1
		else:
			d[i] += 1
	print(m - max(d.values()))


import statistics
from statistics import mode
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	m = mode(a)
	print(n - a.count(m))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	k = len(l)
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	m = max(d.values())
	print(k - m)


testcases = int(input())
for i in range(testcases):
	n = int(input())
	arr = list(map(int, input().split()))
	count = {}
	for c in arr:
		if c not in count:
			count[c] = 1
		else:
			count[c] += 1
	print(len(arr) - max(count.values()))


tests = int(input())
for i in range(tests):
	length = int(input())
	piles_arr = list(map(int, input().split()))
	piles_dict = {}
	for count in piles_arr:
		if count in piles_dict:
			piles_dict[count] += 1
		else:
			piles_dict[count] = 1
	print(length - max(piles_dict.values()))


t = input()
for c in range(0, int(t)):
	n = int(input())
	arr = list(map(int, input().split()))
	sets = {}
	for i in arr:
		if i not in sets:
			sets[i] = 1
		else:
			sets[i] += 1
	print(len(arr) - max(sets.values()))


T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	dic = {}
	for i in arr:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	print(N - max(dic.values()))


for _ in range(int(input())):
	a = int(input())
	n = list(map(int, input().split()))
	dict1 = {}
	for x in n:
		if x in dict1:
			dict1[x] += 1
		else:
			dict1[x] = 1
	print(len(n) - max(dict1.values()))


for i in range(int(input())):
	a = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for i in arr:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	n = list(d.values())
	print(a - max(d.values()))


T = int(input())
for i in range(T):
	n = int(input())
	d = list(map(int, input().split()))
	l = len(d)
	f = {}
	for x in d:
		if x in f:
			f[x] += 1
		else:
			f[x] = 1
	print(l - max(f.values()))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	dic = {}
	for i in l:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	print(n - max(dic.values()))