URI Online Judge | 1690

Subset Sum

By Bruno Adami, ICMC - USP BR Brazil

Timelimit: 1 second

You have in your hands an array of positive integers, not necessarily distinct.

Let's choose some of the numbers in the array, i.e, a non-empty subset of the original array. The value of a subset is the sum of the contained elements.

What is the smallest subset value that cannot be achieved?

For instance, take the array [2, 1, 5]. The following subsets can be formed: [1], [2], [5], [1, 2], [1, 5], [2, 5], [1, 2, 5]. Their values are: 1, 2, 5, 3, 6, 7, 8, respectively. The smallest subset value that cannot be achieved in this case is 4.

Input

The first line will contain a number T (1T ≤ 1000), indicating how many test cases will follow.

For each test case, the first line will contain a number N (1N10000), indicating how many numbers the array contains. The next line will contain N space separated positive integers, ranging from 1 to 109.

Output

For each test case, output a single line, the answer for the problem.

Sample Input Sample Output

3

1

1

1

2

3

2 1 5

2

1

4