Time Limit: 1.0 s

Memory Limit: 512.0 MB

Description

You are given an array \(A\) of \(N\) numbers. You can do the following operations on the array as many time (possibly zero) as you want.

• Chose any element \(X\) from the array, remove the element from the array and add two element \(a,b\) such that \(X = a+b\)

• Chose any two element \(a,b\) from the array, remove them from array and add an element \(X\) to the array such that \(X = a+b\)

What is the maximum possible value of MEX from the array ?

MEX of an array is the minimum non-negative number which is not present in the array.
for example :
MEX of {1,2,4} is 0
MEX of {0,1,3,4} is 2
MEX of {0,1,2} is 3

Input

First line takes an integer \(T\) : number of testcase
first line of each testcase takes an integer \(N\) : size of the array
second line of each testcase takes \(N\) integers \(A1,A2,A3...An\)

\(1 <= T <= 10000\)
\(1 <= N <= 2*10^5\)
\(0 <= Ai <= 10^9\)

sum of \(N\) over all testcase will not exceed \(2*10^5\)

Output

for each testcase output an integer : maximum value of MEX in a new line

Sample

3
3
0 1 2
4
0 1 1 1
3
0 3 3

3
3
4

in first testcase :
You dont need to apply any operation to make the maximum MEX = 3

in second testcase :
apply the second operation once ,chose a = 1, b = 1 and add 1+1=2 to the array, the array becomes {0,2,1} so the MEX is 3

in third testcase :
apply the first operation once, chose X = 3 and add a = 1, b = 2 to the array. the array becomes {0,1,2,3}. so the MEX is 4