There are N different types of colours numbered from 1 to N. Chef has A_{i} balls having colour i, (1≤ i ≤ N).

Chef will arrange some boxes and put each ball in exactly one of those boxes.  
Find the minimum number of boxes Chef needs so that no box contains two balls of same colour.

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

- The first line of input will contain a single integer T, denoting the number of test cases. The description of the test cases follows.
- The first line of each test case contains a single integer N, denoting the number of colors.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} — denoting the number of balls having colour i.

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

For each test case, output the minimum number of boxes required so that no box contains two balls of same colour.

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

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

----- Sample Input 1 ------ 
3
2
8 5
3
5 10 15
4
4 4 4 4

----- Sample Output 1 ------ 
8
15
4

----- explanation 1 ------ 
Test case $1$: Chef needs at least $8$ boxes such that no box has two balls of same colour. A possible configuration of the $8$ boxes would be $\{[1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1], [1], [1]\}$ where the $i^{th}$ element of this set denotes the colour of balls in the $i^{th}$ box.

Test case $2$: Chef needs at least $15$ boxes such that no box has two balls of same colour.

Test case $3$: Chef needs at least $4$ boxes such that no box has two balls of same colour. A possible configuration of the $4$ boxes would be $\{[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]\}$ where the $i^{th}$ element of this set denotes the colour of balls in the $i^{th}$ box.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
for i in range(int(input())):
	N = int(input())
	K = list(map(int, input().split()))
	print(max(K))


T = int(input())
for i in range(0, T):
	n = int(input())
	a = list(map(int, input().split()))
	print(max(a))


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


for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	print(max(x))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(max(l))


T = int(input())
for i in range(T):
	n = int(input())
	p = list(map(int, input().split()))
	print(max(p))


for j in range(int(input())):
	n = int(input())
	k = map(int, input().split())
	print(max(k))


for _ in range(int(input())):
	num_colors = int(input())
	colors = list(map(int, input().split()))
	print(max(colors))


t = int(input())
for i in range(t):
	d = int(input())
	x = list(map(int, input().split(' ')))
	print(max(x))


t = int(input())
for i in range(0, t):
	n = int(input())
	c = list(map(int, input().split()))
	m = max(c)
	print(m)


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	q = 0
	for j in a:
		if int(j) > q:
			q = int(j)
	print(q)


T = int(input())
for i in range(T):
	N = int(input())
	M = list(map(int, input().split()))
	A = max(M)
	print(A)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(max(a))


def colors(a):
	for j in range(n):
		return max(a)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	v = colors(a)
	print(v)


repeat = int(input())
for item in range(repeat):
	numb = int(input())
	a = map(int, input().split())
	print(max(a))


t = int(input())
for i in range(t):
	a = int(input())
	b = list(map(int, input().split()))
	print(max(b))


t = int(input())
for i in range(t):
	n = int(input())
	a1 = map(int, input().split())
	print(max(a1))


t = int(input())
for i in range(t):
	N = int(input())
	a = map(int, input().split())
	print(max(a))


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if a[i] > count:
			count = a[i]
	print(count)


n = int(input())
for i in range(n):
	a = int(input())
	m = list(map(int, input().split()))
	print(max(m))


m1 = int(input())
for i in range(m1):
	r1 = int(input())
	r2 = list(map(int, input().split()))
	print(max(r2))


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	print(max(l))


t = int(input())
for i in range(t):
	n = int(input())
	max = 0
	x = list(map(int, input().split()))
	for i in range(n):
		if x[i] >= max:
			max = x[i]
	print(max)


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	print(max(l))


T = int(input())
for i in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	print(max(l))


T = int(input())
for _ in range(T):
	N = int(input())
	A = map(int, input().split())
	L = list(A)
	print(max(L))


t = int(input())
for i in range(t):
	total_colors = int(input())
	print(max((total for total in map(int, input().split()))))


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


a = int(input())
for i in range(a):
	b = int(input())
	c = [int(x) for x in input().split()]
	print(max(c))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	print(m)


T = int(input())
for _ in range(T):
	N = int(input())
	lst = list(map(int, input().strip().split()))
	print(max(lst))