You are given an array A of N integers. You can do the following two types of operations any (possibly zero) number of times:

Pick two indices i and j (1 ≤ i,j ≤ |A|, i \neq j). Change A_{j} := A_{j} + A_{i} and remove the i^{th} element from the array.
Pick an index i (1 ≤ i ≤ |A|). Split A_{i} into two positive integers X and Y such that X+Y=A_{i}. Remove the i^{th} element from the array and append elements X and Y to the array.

Find the maximum number of distinct elements present in the array after performing any number of operations of the above two types.

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

- The first line contains an integer T denoting the number of test cases. The T test cases then follow.
- The first line of each test case contains an integer N - the size of the array.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}.

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

For each test case, output the maximum number of distinct elements present in the array after performing any number of operations of the above two types.

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

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

----- Sample Input 1 ------ 
2
3
1 2 4
4
1 1 3 4
----- Sample Output 1 ------ 
3
3
----- explanation 1 ------ 
- Test case $1$: The maximum number of distinct elements that can be achieved by performing some finite number of operations on the given array is $3$. Some examples of the final array are:
- $[1, 2, 4]$ : Perform no operation on the given array.
- $[1, 2, 1, 3]$ : Perform operation $2$. Choose $i = 3$. Here, $A_{3} = 4$. Break it as $X = 1$ and $Y = 3$. On removing $A_{3}$ and appending $X$ and $Y$, we get $[1, 2, 1, 3]$. This array has $3$  distinct elements.

- Test case $2$: The maximum number of distinct elements that can be achieved by performing some finite number of operations on the given array is $3$. Some examples of the final array are:
- $[1, 1, 3, 4]$ : Perform no operation on the given array.
- $[1, 1, 3, 2, 2]$ : Perform operation $2$. Choose $i = 4$. Here, $A_{4} = 4$. Break it as $X = 2$ and $Y = 2$. On removing $A_{4}$ and appending $X$ and $Y$, we get $[1, 1, 3, 2, 2]$. This array has $3$  distinct elements.
- $[2, 3, 4]$ : Perform operation $1$. Choose $i = 1$ and $j=2$. On changing $A_{2} := A_{1}+A_{2} = 1+1=2$ and removing $A_{1}$, we get $[2, 3, 4]$. This array has $3$  distinct elements.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	total = sum(list(map(int, input().split())))
	i = 1
	while True:
		if total < i * (i + 1) // 2:
			break
		i += 1
	print(i - 1)


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	a = 1
	b = 1
	c = -(2 * s)
	v1 = math.floor((-b + (b ** 2 - 4 * a * c) ** 0.5) / (2 * a))
	v2 = math.floor((-b - (b ** 2 - 4 * a * c) ** 0.5) / (2 * a))
	if v1 >= v2:
		print(v1)
	else:
		print(v2)


import math

def find_largest_N(A):
	low = 0
	high = A
	while low < high - 1:
		mid = (low + high) // 2
		if mid * (mid + 1) // 2 <= A:
			low = mid
		else:
			high = mid
	return low
for _ in range(int(input())):
	n = int(input())
	a = sum([int(x) for x in input().split()])
	print(find_largest_N(a))


import math

def find_largest_N(A):
	N = (-1 + math.sqrt(1 + 8 * A)) / 2
	N = math.floor(N)
	return N
for _ in range(int(input())):
	n = int(input())
	a = sum([int(x) for x in input().split()])
	print(find_largest_N(a))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	i = 1
	ans = 0
	while s >= 0:
		s = s - i
		ans = ans + 1
		i = i + 1
	print(ans - 1)


from math import ceil, sqrt
for _ in range(int(input())):
	n = int(input())
	lst = [int(x) for x in input().split()]
	sum = 0
	for i in lst:
		sum += i
	d = 1 + 8 * sum
	root = int((-1 + sqrt(d)) / 2)
	print(root)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	s1 = 0
	ans = 0
	for j in range(1, 1000000):
		s1 += j
		if s1 <= s:
			ans += 1
		else:
			break
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	s1 = 0
	c = 0
	for j in range(1, 1000000):
		s1 += j
		if s >= s1:
			c += 1
		else:
			break
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = sum(list(map(int, input().split())))
	x = 0
	c = 0
	for i in range(1, lst):
		x = x + i
		if x > lst:
			break
		c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	total = sum(a)
	for i in range(1, total):
		x = i * (i + 1) / 2
		if x > total:
			break
	print(i - 1)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	x = 1
	i = 2
	c = 0
	while x <= s:
		x += i
		c += 1
		i += 1
	print(c)
	t -= 1


t = int(input(''))
for _ in range(t):
	n = int(input(''))
	l = list(map(int, input().split()))
	s = sum(l)
	for i in range(1, s):
		x = i * (i + 1) / 2
		if x > s:
			break
	print(i - 1)


for test in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	i = 1
	while True:
		if i * (i + 1) // 2 > s:
			break
		else:
			i += 1
	print(i - 1)


for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	sum2 = sum(list1)
	list2 = []
	z = 1
	while True:
		if sum2 - z >= 0:
			list2.append(z)
			sum2 = sum2 - z
		else:
			break
		z += 1
	print(len(list2))


import math
for i in range(int(input())):
	n = int(input())
	s = sum(map(int, input().split()))
	ans = math.ceil((s * 2) ** 0.5)
	while ans * (ans + 1) / 2 > s:
		ans -= 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = sum(l)
	an = 0
	while an * (an + 1) <= 2 * a:
		an += 1
	print(an - 1)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	Sum = sum(a)
	i = 1
	while 1:
		if i * (i + 1) // 2 >= Sum:
			if i * (i + 1) // 2 == Sum:
				print(i)
			else:
				print(i - 1)
			break
		i += 1


t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	total = sum(li)
	m = 1
	while total >= m:
		total -= m
		m += 1
	print(m - 1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = sum(arr)
	n = 1
	while n * (n + 1) <= s * 2:
		n += 1
	print(n - 1)


t = input()
for c in range(0, int(t)):
	num_of_items = input()
	sequence = map(int, input().split(' '))
	sequence = list(sequence)
	sum_of_sequence = sum(sequence)
	n = (pow(1 + 8 * sum_of_sequence, 0.5) - 1) // 2
	print(int(n))


get_int = lambda : int(input())
get_mint = lambda : list(map(int, input().split()))
for _ in range(get_int()):
	N = get_int()
	print(int(-1 + (1 + 8 * sum(get_mint())) ** 0.5) // 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	add = sum(a)
	c = 0
	for i in range(1, add):
		if add < i:
			break
		add -= i
		c += 1
	print(c)


def split(n):
	summ = sum(n)
	i = 1
	while summ >= 0:
		summ -= i
		i += 1
	return i - 2
for _ in range(int(input())):
	s = int(input())
	print(split(list(map(int, input().split()))))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sumA = sum(a)
	cnt = 0
	for i in range(1, sumA):
		if sumA < i:
			break
		sumA -= i
		cnt += 1
	print(cnt)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = sum(a)
	j = 0
	k = 1
	while k <= m:
		m -= k
		j += 1
		k += 1
	print(j)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	t = sum(arr)
	i = 1
	c = 0
	while i <= t:
		t -= i
		i += 1
		c += 1
	print(c)


for _ in range(int(input())):
	nn = int(input())
	ll = list(map(int, input().split()))
	ss = sum(ll)
	ii = 1
	count = 0
	while ii <= ss:
		ss -= ii
		ii += 1
		count += 1
	print(count)


T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split(' ')]
	count = sum(A)
	ans = 0
	i = 1
	while count > 0:
		count = count - i
		if count >= 0:
			ans += 1
		i = i + 1
	print(ans)


for i in range(int(input())):
	u = int(input())
	tot = sum(list(map(int, input().split())))
	ans = 0
	k = 1
	while k <= tot:
		tot = tot - k
		k = k + 1
		ans = ans + 1
	print(ans)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	sm = sum(A)
	for i in range(1, sm):
		if i * (i + 1) // 2 > sm:
			print(i - 1)
			break


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	sum_ = sum(l)
	c = 0
	i = 0
	while c <= sum_:
		i += 1
		c += i
	ans = i - 1
	print(ans)
	t -= 1


n = int(input())
for i in range(n):
	q = int(input())
	l = list(map(int, input().split()))
	a = set(l)
	k = sum(l)
	o = 1
	s = 0
	while k > 0 and k >= o:
		k = k - o
		s = s + 1
		o = o + 1
	print(s)


import math
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	x = 1
	sum_ = sum(arr)
	while x ** 2 + x <= 2 * sum_:
		x += 1
	ans = x - 1
	print(ans)


import math

def cal_total(x):
	return x * (x + 1) // 2
tests = int(input())
for i in range(tests):
	length = int(input())
	total = sum(map(int, input().split()))
	ans = math.ceil((total * 2) ** 0.5)
	while cal_total(ans) > total:
		ans -= 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	list1 = sum(list(map(int, input().split())))
	count = 1
	while list1 >= 0:
		list1 = list1 - count
		count = count + 1
	print(count - 2)


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	sum_ = sum(li)
	c = 0
	i = 0
	while c <= sum_:
		i += 1
		c += i
	ans = i - 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	sum_ = sum(li)
	c = 0
	for i in range(1, sum_ + 1):
		c += i
		if c > sum_:
			ans = i - 1
			break
	if sum_ < 3:
		ans = 1
	print(ans)


def il():
	return [int(a) for a in input().strip().split()]

def ii():
	return int(input())
for i in range(ii()):
	x = ii()
	l = il()
	summ = sum(l)
	ans = 0
	k = 1
	while summ - k >= 0:
		summ -= k
		k += 1
		ans += 1
	print(ans)


from bisect import bisect_left, bisect_right
import math
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	n = ii()
	l = il()
	s = sum(l)
	i = 1
	ans = 0
	while s - i >= 0:
		s = s - i
		i += 1
		ans += 1
	print(ans)


import math
from collections import Counter
from itertools import combinations, permutations

def solve():
	n = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	x = sum(arr)
	i = 1
	while True:
		a = i * (i + 1) / 2
		if a < x:
			i += 1
		if a == x:
			print(i)
			break
		if a > x:
			print(i - 1)
			break
for _ in range(int(input())):
	solve()


from math import gcd, sqrt, ceil, floor, log10
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
sys.setrecursionlimit(3000000)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(1000000000.0) + 7
NEWLINE = '\n'
SPACE = ' '
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))

def solve(*args, **kwargs):
	(n, arr) = args
	total = sum(arr)
	(i, sum_) = (1, 0)
	while sum_ + i <= total:
		sum_ += i
		i += 1
	return i - 1

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg1 = inp(int)
		arg2 = inp_vars(int, SPACE)
		res = solve(*(arg1, arg2))
		if type(res) in {list, tuple, set}:
			print(*res, sep=' ')
		else:
			print(res)
main()


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		nums = list(map(int, input().split()))
		summ = sum(nums)
		ans = 0
		k = 1
		while k <= summ:
			summ -= k
			ans += 1
			k += 1
		print(ans)
except:
	pass


def main():
	from sys import stdin, stdout
	from collections import Counter
	t = int(stdin.readline())

	def f(tot, s, i):
		while s + i <= tot:
			s += i
			i += 1
		return i - 1
	for i in range(t):
		n = int(stdin.readline())
		(*l,) = map(int, stdin.readline().split())
		print(f(sum(l), 0, 1), file=stdout, flush=True)
main()


def main():
	from sys import stdin, stdout
	from collections import Counter
	t = int(stdin.readline())

	def f(tot, s, i):
		while s + i <= tot:
			s += i
			i += 1
		return i - 1
	for i in range(t):
		n = int(stdin.readline())
		(*l,) = map(int, stdin.readline().split())
		stdout.write(str(f(sum(l), 0, 1)) + '\n')
main()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	x = 1
	sumArr = sum(arr)
	while x ** 2 + x <= 2 * sumArr:
		x += 1
	print(x - 1)


T = int(input())
for x in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	an = 0
	k = 1
	while s >= 0:
		s -= k
		k += 1
		an += 1
	print(an - 1)


T = int(input())
for i in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	msum = sum(a)
	ans = 0
	k = 1
	while msum >= 0:
		msum -= k
		k += 1
		ans += 1
	ans -= 1
	print(ans)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	k = 0
	while k * (k + 1) <= 2 * s:
		k += 1
	print(k - 1)


def unique(li):
	s = sum(li)
	i = 1
	curr_s = 0
	while curr_s + i <= s:
		curr_s += i
		i += 1
	return i - 1
for _ in range(int(input())):
	n = input()
	li = list(map(int, input().split()))
	print(unique(li))


for _ in range(int(input())):
	input()
	print(int((2 * sum((int(s) for s in input().split())) + 0.25) ** 0.5 - 0.5))


from math import sqrt
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	sum = 0
	for j in l:
		sum += j
	print(int((sqrt(8 * sum + 1) - 1) / 2))


T = int(input())
for i in range(0, T):
	a = int(input())
	b = input().split()
	sums = 0
	for j in range(0, a):
		b[j] = int(b[j])
		sums += b[j]
	for j in range(0, sums):
		if sums < j * (j + 1) // 2:
			print(j - 1)
			break


import math
for tc in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	d = 8 * s
	print((-1 + int(math.sqrt(d + 1))) // 2)


tc = int(input())
for _ in range(1, 1 + tc):
	n = int(input())
	nums = list(map(int, input().split()))
	tot = sum(nums)
	summ = 0
	i = 1
	while True:
		if summ + i > tot:
			break
		summ += i
		i += 1
	print(i - 1)


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split(' ')))
	s = sum(l)
	i = 1
	c = 0
	while s >= i:
		s -= i
		i += 1
		c += 1
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	sum1 = sum(a)
	sum2 = 0
	for i in range(1, 100000):
		sum2 += i
		if sum2 == sum1:
			print(i)
			break
		elif sum2 > sum1:
			print(i - 1)
			break


for tc in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	l = 0
	for i in range(1, 100000):
		l += i
		if l == s:
			print(i)
			break
		elif l > s:
			print(i - 1)
			break


for M in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	su = 0
	for i in range(1, 1000000):
		su += i
		if su == s:
			print(i)
			break
		elif su > s:
			print(i - 1)
			break


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sumana = sum(a)
	i = 1
	ans = 0
	while sumana >= 0:
		ans += 1
		sumana -= i
		i += 1
	print(ans - 1)


case = int(input())
for _ in range(case):
	N = int(input())
	li = list(map(int, input().split(' ')))
	total = sum(li)
	ans = 0
	while total >= 0:
		total -= ans + 1
		if total < 0:
			break
		ans += 1
	print(ans)