Tokitsukaze has a sequence $a$ of length $n$. For each operation, she selects two numbers $a_i$ and $a_j$ ($i \ne j$; $1 \leq i,j \leq n$).

If $a_i = a_j$, change one of them to $0$.

Otherwise change both of them to $\min(a_i, a_j)$.

Tokitsukaze wants to know the minimum number of operations to change all numbers in the sequence to $0$. It can be proved that the answer always exists.


-----Input-----

The first line contains a single positive integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

For each test case, the first line contains a single integer $n$ ($2 \leq n \leq 100$) — the length of the sequence $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 100$) — the sequence $a$.


-----Output-----

For each test case, print a single integer — the minimum number of operations to change all numbers in the sequence to $0$.


-----Examples-----

Input
3
3
1 2 3
3
1 2 2
3
1 2 0
Output
4
3
2


-----Note-----

In the first test case, one of the possible ways to change all numbers in the sequence to $0$:

In the $1$-st operation, $a_1 < a_2$, after the operation, $a_2 = a_1 = 1$. Now the sequence $a$ is $[1,1,3]$.

In the $2$-nd operation, $a_1 = a_2 = 1$, after the operation, $a_1 = 0$. Now the sequence $a$ is $[0,1,3]$.

In the $3$-rd operation, $a_1 < a_2$, after the operation, $a_2 = 0$. Now the sequence $a$ is $[0,0,3]$.

In the $4$-th operation, $a_2 < a_3$, after the operation, $a_3 = 0$. Now the sequence $a$ is $[0,0,0]$.

So the minimum number of operations is $4$.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
for s in [*open(0)][2::2]:
	n = len((a := s.split()))
	m = a.count('0')
	print(n - m if m else n if len({*a}) < n else n + 1)


import sys
input = lambda : sys.stdin.readline().strip()
t = int(input())
for i in range(t):
	l = int(input())
	arr = list(map(int, input().split()))
	if arr.count(0) > 0:
		print(l - arr.count(0))
	elif len(set(arr)) < l:
		print(l)
	else:
		print(l + 1)


for s in [*open(0)][2::2]:
	n = len((a := s.split()))
	print(n + (-a.count('0') or len({*a}) == n))


from sys import stdin
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
ceil_div = lambda a, b: -(-a // b)
mod = 10 ** 9 + 7
for _ in range(rn()):
	n = rn()
	a = rl()
	ans = 0
	if 0 in a:
		ans = n - a.count(0)
	elif len(set(a)) == n:
		ans = n + 1
	else:
		ans = n
	print(ans)


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


t = int(input())
v = []

def same(a):
	return len(set(a)) != len(a)

def min_steps(a, b):
	zer = b.count(0)
	if zer != 0:
		return a - zer
	elif same(b):
		return a
	else:
		return a + 1
for i in range(t):
	v.append([int(input())])
	b = [int(x) for x in input().split()]
	v[i].append(b)
for i in v:
	print(min_steps(i[0], i[1]))


import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if 0 in a:
		zero = a.count(0)
		print(n - zero)
	else:
		a.sort()
		if len(set(a)) != n:
			print(n)
		else:
			print(n + 1)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a.count(0) > 0:
		print(n - a.count(0))
	elif len(set(a)) < n:
		print(n)
	else:
		print(n + 1)


n = int(input())
while n > 0:
	num = int(input())
	ls = list(map(int, input().split()))
	if ls.count(0) > 0:
		print(num - ls.count(0))
	elif len(set(ls)) < num:
		print(num)
	else:
		print(num + 1)
	n -= 1


for j in range(0, int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s1 = set(l)
	if 0 in l:
		print(n - l.count(0))
	elif len(l) == len(s1):
		print(n + 1)
	elif len(l) != len(s1):
		print(n)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if 0 in arr:
		c = arr.count(0)
		print(n - c)
	elif len(set(arr)) != n:
		print(n)
	else:
		print(n + 1)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	srr = set(arr)
	zeros = 0
	for e in arr:
		if e == 0:
			zeros += 1
	if zeros == 0 and len(srr) == n:
		print(n + 1)
	elif zeros == 0:
		print(n)
	else:
		print(n - zeros)


n = int(input())

def main(numbers, lens):
	zeroes = numbers.count(0)
	if zeroes == 0:
		if len(numbers) == len(set(numbers)):
			return lens + 1
		else:
			return lens
	else:
		return lens - zeroes
answer = []
for i in range(n):
	num = int(input())
	numbers = list(map(int, input().split()))
	answer.append(main(numbers, num))
for elem in answer:
	print(elem)


t = int(input())
for i in range(t):
	l = int(input())
	x = [y for y in input().split()]
	if '0' in x:
		c = x.count('0')
		print(l - c)
		continue
	if len(set(x)) == len(x):
		print(l + 1)
	else:
		print(l)


n = int(input())
c = 0
for x in range(n):
	size = int(input())
	values = input().split()
	count_of_zero = values.count('0')
	size_of_set = len(set(values))
	if size_of_set == size and count_of_zero == 0:
		print(size + 1)
	elif size < size_of_set:
		print(size)
	else:
		print(size - count_of_zero)


t = int(input())
while t > 0:
	c = 0
	n = int(input())
	li = list(map(int, input().split()))
	l = li.count(0)
	if l > 0:
		print(len(li) - l)
	elif len(li) != len(set(li)):
		print(len(li))
	else:
		print(len(li) + 1)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(ii) for ii in input().split()]
	ans = 0
	for i in a:
		if i == 0:
			ans += 1
	if ans != 0:
		print(n - ans)
	elif len(set(a)) == n:
		print(n + 1)
	else:
		print(n)


from math import inf, gcd, log, log2, floor, ceil, sqrt
from collections import Counter, defaultdict
from heapq import heappush, heappop, heapify
from functools import lru_cache
import sys
DIRS = [[1, 0], [0, 1], [0, -1], [-1, 0], [-1, -1], [1, 1], [-1, 1], [1, -1]]
MOD = 10 ** 9 + 7
input = sys.stdin.readline
t = int(input())

def solve():
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	c = Counter(a)
	if 0 in c:
		print(n - c[0])
		return
	else:
		for (k, v) in c.items():
			if v >= 2:
				print(n)
				return
		print(n + 1)
		return
while t:
	solve()
	t -= 1


from sys import stdin, stdout
import collections
import math

def solve():
	return

def main():
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		f = 0 in l or len(l) != len(set(l))
		if f:
			ans = len(l) - l.count(0)
		else:
			ans = len(l) + 1
		print(ans)
	return
input = stdin.readline
main()


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	if 0 in lst:
		print(n - lst.count(0))
	elif len(lst) == len(set(lst)):
		print(n + 1)
	else:
		print(n)


import sys
from collections import Counter

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

def main():
	t = int(input())
	for tc in range(t):
		n = int(input())
		nums = list(map(int, input().split()))
		num_zero = nums.count(0)
		if num_zero:
			print(n - num_zero)
		elif Counter(nums).most_common(1)[0][1] >= 2:
			print(n)
		else:
			print(n + 1)
main()


import sys

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

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

def main():
	for _ in range(int(input())):
		n = int(input())
		ls = get_ls()
		z = 0
		st = set(ls)
		for i in ls:
			if i == 0:
				z += 1
		if z > 0:
			print(n - z)
		elif len(st) == n:
			print(n + 1)
		else:
			print(n)
main()


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a.count(0) != 0:
		ans.append(n - a.count(0))
	elif len(a) == len(set(a)):
		ans.append(n + 1)
	else:
		ans.append(n)
for elem in ans:
	print(elem)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	h = l.count(0)
	if h > 0:
		print(n - h)
	elif len(set(l)) != len(l):
		print(n)
	else:
		print(n + 1)


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


count = int(input())
for _ in range(count):
	n = int(input())
	array = [int(v) for v in input().split()]
	if 0 in array:
		print(n - array.count(0))
	elif len(set(array)) == len(array):
		print(n + 1)
	else:
		print(n)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	if 0 in a:
		print(n - a.count(0))
	elif len(list(set(a))) < len(a):
		print(n)
	else:
		print(n + 1)
	t = t - 1


import sys
input = lambda : sys.stdin.readline().strip()
for i in range(int(input())):
	a = int(input())
	lis = list(map(int, input().split()))
	l = len(set(lis))
	if 0 in lis:
		print(a - lis.count(0))
	elif l < a:
		print(a)
	elif l == a:
		print(a + 1)


t1 = int(input())
for i in range(t1):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0 in a
	if l:
		print(len(a) - a.count(0))
	else:
		a1 = set(a)
		if len(a1) < len(a):
			print(len(a))
		else:
			print(len(a) + 1)


for i in range(int(input())):
	y = int(input())
	x = list(map(int, input().split()))
	z = x.count(0)
	xz = set(x)
	xy = len(xz)
	if z > 0:
		print(y - z)
	elif y == xy and z <= 0:
		print(y + 1)
	else:
		print(y)


t = int(input())

def checkIfDuplicates_1(listOfElems):
	if len(listOfElems) == len(set(listOfElems)):
		return False
	else:
		return True
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	z = l.count(0)
	if z == 0:
		g = checkIfDuplicates_1(l)
		if g:
			print(len(l))
		else:
			a = len(l)
			a += 1
			print(a)
	else:
		print(len(l) - z)


for i in range(int(input())):
	a = int(input())
	s = list(map(int, input().split()))
	t = 10 ** 8
	if 0 in s:
		print(len(s) - s.count(0))
	elif len(s) != len(set(s)):
		print(len(s))
	else:
		print(len(s) + 1)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	if n == len(s):
		ans = n + 1
	elif n > len(s):
		ans = n
	c = a.count(0)
	if 0 in a:
		ans = n - c
	print(ans)


for _ in range(int(input())):
	l = int(input())
	arr = list(map(int, input().split()))
	if 0 in arr:
		print(len(arr) - arr.count(0))
	elif len(arr) == len(set(arr)):
		print(l + 1)
	else:
		print(l)


for i in range(int(input())):
	x = int(input())
	y = list(map(int, input().split()))
	if 0 in y:
		print(len(y) - y.count(0))
	elif len(set(y)) == x:
		print(x + 1)
	else:
		print(x)


t = int(input())
for _ in range(t):
	n = int(input())
	sequence = list(map(int, input().split()))
	count_zeros = sequence.count(0)
	if count_zeros:
		print(len(sequence) - count_zeros)
	elif len(set(sequence)) < len(sequence):
		print(len(sequence))
	else:
		print(len(sequence) + 1)


def num_of_steps(list, length):
	if 0 in list:
		return sum([1 for e in list if e != 0])
	else:
		return length if len(set(list)) != length else length + 1
num_cases = int(input())
for _ in range(num_cases):
	length = int(input())
	seq_list = list(map(int, input().split()))
	print(num_of_steps(seq_list, length))


case = int(input())
for _ in range(case):
	n = int(input())
	l = list(map(int, input().split()))
	c = l.count(0)
	if c == 0 and len(set(l)) == n:
		print(n + 1)
	elif c == 0 and len(set(l)) != n:
		print(n)
	else:
		print(n - c)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = {}
	for num in arr:
		if num not in cnt:
			cnt[num] = 0
		cnt[num] += 1
	if 0 in cnt:
		return n - cnt[0]
	return n + 1 if len(cnt) == n else n
for _ in range(int(input())):
	print(solve())


for i in range(int(input())):
	num = int(input())
	values = list(map(int, input().split()))
	ch = values.count(0)
	if 0 in values:
		print(num - ch)
	elif num == len(set(values)):
		print(num + 1)
	else:
		print(num)


t1 = int(input())
for hi in range(t1):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0 in a
	if l:
		print(n - a.count(0))
	else:
		p = set(a)
		if len(p) < len(a):
			print(len(a))
		else:
			print(len(a) + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	cnt = l.count(0)
	if len(l) == len(s) and cnt == 0:
		print(len(l) + 1 - cnt)
	else:
		print(len(l) - cnt)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	k = 0
	if len(a) == len(s) and 0 not in a:
		k = 2
		a[0] = 0
	if len(a) != len(s) and 0 not in a:
		k = 1
		a[0] = 0
	if 0 in a:
		ls = [x for x in a if x != 0]
		print(len(ls) + k)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if 0 in l:
		num = 0
		for i in range(n):
			if l[i] == 0:
				num = num + 1
		print(len(l) - num)
	else:
		s = set(l)
		if len(s) == len(l):
			print(len(s) + 1)
		else:
			print(len(l))


testcases = int(input())
for i in range(testcases):
	n = int(input())
	li = list(map(int, input().split()))
	z = set(li)
	if len(z) == len(li):
		if 0 in z:
			print(len(li) - 1)
		else:
			print(len(li) + 1)
	elif 0 in z:
		print(len(li) - li.count(0))
	else:
		print(len(li))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = l.count(0)
	if c > 0:
		print(n - c)
	else:
		k = set(l)
		k = list(k)
		if len(k) == len(l):
			print(n + 1)
		else:
			print(n)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = set(l)
	b = l.count(0)
	if b > 0:
		print(n - b)
	elif len(a) == len(l):
		print(n + 1)
	else:
		print(n)


for i in range(int(input())):
	m = int(input(''))
	list1 = list(map(int, input().split()))
	if 0 in list1:
		print(m - list1.count(0))
	elif len(set(list1)) == len(list1):
		print(m + 1)
	else:
		print(m)


case = int(input())
for _ in range(case):
	n = int(input())
	l = input().split()
	nums = set()
	zero = 0
	for elem in l:
		if elem == '0':
			zero += 1
		else:
			nums.add(int(elem))
	if zero > 0:
		print(n - zero)
	elif len(nums) < n:
		print(n)
	else:
		print(n + 1)


for _ in range(int(input())):
	int(input())
	a = sorted(map(int, input().split()))
	cnt = 0
	n = len(a)
	if 0 in a:
		cnt = n - a.count(0)
	elif len(set(a)) < n:
		cnt = n
	else:
		cnt = n + 1
	print(cnt)


for inh in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if 0 in a:
		print(n - a.count(0))
	else:
		b = set(a)
		if len(a) == len(b):
			print(n + 1)
		else:
			print(n)


cases = int(input())

def do():
	_ = input()
	arr = list(map(int, input().split()))
	n = len(arr)
	number_of_zeros = arr.count(0)
	if number_of_zeros > 0:
		print(n - number_of_zeros)
	elif len(set(arr)) < n:
		print(n)
	else:
		print(n + 1)
for i in range(cases):
	do()


t = int(input())
for x in range(t):
	n = int(input())
	lst = list(input().split())
	lst.sort(reverse=1)
	z = lst.count('0')
	if z > 0:
		lst = lst[:-z]
		print(len(lst))
	elif n > 2:
		l = len(lst)
		lst = list(set(lst))
		ll = len(lst)
		if ll == l:
			print(1 + l)
		else:
			print(l)
	elif lst[0] != lst[1]:
		print(3)
	else:
		print(2)


t = int(input())
while t:
	t -= 1
	input()
	a = list(map(int, input().split(' ')))
	sa = set(a)
	z = a.count(0)
	if z:
		print(len(a) - z)
	elif len(sa) == len(a):
		print(len(a) + 1)
	else:
		print(len(a))


for t in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	print(n + (-a.count(0) or len(set(a)) == n))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if 0 not in arr and len(set(arr)) == n:
		print(n + 1)
	else:
		print(n - arr.count(0))


def cal(n, arr):
	t = arr.count(0)
	if t == n:
		return 0
	if t > 0:
		return n - t
	s = len(set(arr))
	if s < n:
		return n
	return n + 1
for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	print(cal(n, arr))


p = int(input())
for i in range(p):
	s = int(input())
	l = [int(i) for i in input().split()]
	se = set(l)
	if 0 in l:
		print(len(l) - l.count(0))
	elif len(l) == len(se):
		print(len(l) + 1)
	else:
		print(len(l))


n = int(input())
for i in range(n):
	a = int(input())
	arr = list(map(int, input().split()))
	count_0 = arr.count(0)
	if count_0 > 0:
		print(a - count_0)
	else:
		brr = arr
		set_b = set(brr)
		if len(arr) == len(set_b):
			print(a + 1)
		else:
			c = max(a, a - len(set_b))
			print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ans = 0
	if 0 in arr:
		ans = n - arr.count(0)
	elif len(set(arr)) == n:
		ans = n + 1
	else:
		ans = n
	print(ans)