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.

见题面

见题面