Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef likes to mix colors a lot. Recently, she was gifted N colors A_{1}, A_{2}, ..., A_{N} by her friend.

Chef wants to make the values of all her colors pairwise distinct, as they will then look stunningly beautiful. In order to achieve that, she can perform the following mixing operation zero or more times:

Choose any two colors. Let's denote their values by x and y.
Mix the color with value x into the color with value y. After the mixing, the value of the first color remains x, but the value of the second color changes to x + y.

Find the minimum number of mixing operations Chef needs to perform to make her colors beautiful.

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

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of colors.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting Chef's initial colors.

------ Output ------ 

For each test case, print a single line containing one integer — the minimum number of required mixing operations.

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

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9} for each valid i$

------ Subtasks ------ 

Subtask #1 (30 points): 1 ≤ N ≤ 100

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
2
3
1 2 3
3
2 1 2
----- Sample Output 1 ------ 
0
1
----- explanation 1 ------ 
Example case 1: No two colors have the same value. Hence, they are already beautiful. No mixing is required.

Example case 2: Take the second color (with value x = 1) and mix it into the first color (with value x = 2). After the mixing, the colors will be 3 1 2. Now the colors are beautiful. This is the minimum number of mixing operations that are required. Hence, the answer is 1.

Difficulty: MEDIUM
Tags: Sorting

Constructive algorithms

Data structures

Ad-hoc
Skill types: Sorting

Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(n - len(set(arr)))


for _ in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())))
	(i, count) = (0, 0)
	while i < n - 1:
		if l[i] == l[i + 1]:
			count += 1
		i += 1
	print(count)


t = int(input())
for q in range(t):
	n = int(input())
	s = set(map(int, input().split()))
	print(n - len(s))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	print(len(a) - len(s))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	print(len(l) - len(s))


for _______________________________ in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	print(n - len(set(k)))


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


t = int(input())
for _ in range(t):
	n = int(input())
	a = input().split()
	d = {}
	l = 0
	for i in a:
		d[i] = d.get(i, 0) + 1
		if d[i] != 1:
			l += 1
	print(l)


for _ 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
	s = 0
	for i in d:
		if d[i] > 1:
			s += d[i] - 1
	print(s)


i = int(input())
listk = []
for _ in range(i):
	k = int(input())
	tt = input().split()
	tt2 = []
	for ele in tt:
		tt2.append(int(ele))
	dic = {}
	for ele in tt2:
		if ele not in dic.keys():
			dic[ele] = 1
		else:
			dic[ele] = dic[ele] + 1
	nop = 0
	for ele in dic.keys():
		nop = nop + dic[ele] - 1
	listk.append(nop)
for ele in listk:
	print(ele)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 0
	for (x, y) in Counter(a).items():
		ans += y - 1
	print(ans)


for i in range(int(input())):
	a = int(input())
	x = list(map(int, input().split()))
	s = set(x)
	if len(s) == a:
		print(0)
	else:
		print(a - len(s))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	if len(s) == n:
		print(0)
	else:
		print(n - len(s))


from collections import Counter as c
for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	print(a - len(set(l)))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(abs(len(set(l)) - n))


for _ in range(int(input())):
	n = int(input())
	col = list(map(int, input().split()))
	dic = {}
	for i in col:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	l1 = sorted(col)
	if n == len(dic):
		print(0)
	else:
		cnt = 0
		for i in range(n):
			if dic[col[i]] > 1:
				for j in l1:
					if col[i] + j in dic:
						continue
					else:
						dic[col[i]] -= 1
						col[i] += j
						cnt += 1
						break
		print(cnt)


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	print(x - len(set(l)))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	different = arr[0]
	count = 0
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			arr[i] += different
			different = arr[i]
			count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split(' ')))
	len1 = len(list1)
	list2 = list(set(list1))
	len2 = len(list2)
	print(len1 - len2)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	k = set(l)
	print(len(l) - len(k))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	memo = {}
	c = 0
	for i in arr:
		memo[i] = memo.get(i, 0) + 1
	for i in memo:
		if memo[i] > 1:
			c += memo[i] - 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(n - len(set(a)))


for _ in range(int(input())):
	print(int(input()) - len(set(map(int, input().split(' ')))))


for _ in range(int(input())):
	(n, c) = (int(input()), len(set(map(int, input().split(' ')))))
	print(n - c)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	print(n - len(s))


def main(colors):
	colorFreq = {}
	for color in colors:
		if color not in colorFreq:
			colorFreq[color] = 0
		colorFreq[color] = colorFreq[color] + 1
	cnt = 0
	for color in colorFreq:
		if colorFreq[color] > 1:
			cnt = cnt + colorFreq[color] - 1
	return cnt
try:
	n = int(input())
	for i in range(0, n):
		N = int(input())
		colors = list(map(int, input().split()))
		print(main(colors))
except EOFError as e:
	print()


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = set(a)
	print(n - len(a))


for i in range(0, int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	se = set(li)
	print(n - len(se))


t = int(input())
for _ in range(t):
	n = int(input())
	colors = list(map(int, input().split()))
	print(n - len(set(colors)))


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	c = 0
	A.sort()
	for i in range(1, len(A)):
		if A[i - 1] == A[i]:
			c += 1
	print(c)


tt = int(input())
for ttt in range(tt):
	n = int(input())
	thislist = list(map(int, input().split()))
	thislist.sort()
	ans = 0
	for x in range(1, len(thislist)):
		if thislist[x] == thislist[x - 1]:
			ans += 1
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().strip().split()))
	l.sort()
	count = 0
	for i in range(n - 1):
		if l[i] == l[i + 1]:
			count += 1
	print(count)
	t -= 1


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	print(n - len(set(l)))
	t -= 1


t = int(input())
from collections import Counter
for _ in range(t):
	n = int(input())
	lst = sorted(list(map(int, input().split())))
	xl = Counter(lst)
	val = [xl[i] - 1 for i in xl if xl[i] > 1]
	print(sum(val))


t = int(input())
for x in range(t):
	n = int(input())
	a = [int(c) for c in input().split()]
	print(n - len(set(a)))


tt = int(input())
while tt > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	s = set(l)
	print(n - len(s))
	tt = tt - 1


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	f = set(b)
	c = len(f)
	print(len(b) - c)


t = int(input())
for i in range(t):
	c = int(input())
	list_a = list(map(int, input().split()))
	l1 = len(list_a)
	set_a = set(list_a)
	l2 = len(set_a)
	print(l1 - l2)


from collections import Counter

def ans():
	n = int(input())
	l = list(map(int, input().split()))
	return n - len(set(l))
for _ in range(int(input())):
	print(ans())


T = int(input())
for I in range(T):
	s = 0
	n = int(input())
	a = []
	f = {}
	a = [int(i) for i in input().split()]
	for i in a:
		if i in f:
			f[i] += 1
		else:
			f[i] = 1
	for i in f:
		s += f[i] - 1
	print(s)


for _ in range(int(input())):
	i = int(input())
	j = list(map(int, input().split()))
	print(i - len(set(j)))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = dict()
	for i in l:
		d[i] = 0
	for i in l:
		d[i] += 1
	f = True
	for i in d:
		if d[i] > 1:
			f = False
			break
	if f:
		print('0')
		continue
	if len(d.keys()) == 1:
		print(n - 1)
		continue
	print(len(l) - len(set(l)))


T = int(input())
for i in range(T):
	size = int(input())
	l = list(map(int, input().split()))
	print(size - len(set(l)))


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	l.sort()
	c = 0
	for i in range(1, a):
		if l[i] == l[i - 1]:
			c += 1
	print(c)


for _ 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
	ans = 0
	for (x, y) in d.items():
		if y > 1:
			ans = ans + y - 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	f = {l[0]}
	for i in range(1, len(l)):
		f.add(l[i])
	print(len(l) - len(f))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = dict(Counter(a))
	res = 0
	for i in b:
		if b[i] > 1:
			res += b[i] - 1
	print(res)


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


t = int(input())
for i in range(t):
	n = int(input())
	k = list(map(int, input().split()))
	print(n - len(set(k)))


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


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	if len(A) == len(set(A)):
		print(0)
	else:
		print(len(A) - len(set(A)))