Subset Sum
By Bruno Adami, ICMC - USP 
Brazil
By Bruno Adami, ICMC - USP Brazil
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.
The first line will contain a number T (1 ≤ T ≤ 1000), indicating how many test cases will follow.
For each test case, the first line will contain a number N (1 ≤ N ≤ 10000), indicating how many numbers the array contains. The next line will contain N space separated positive integers, ranging from 1 to 109.
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 |