Smallest Nonrepresentable Sum

You are given an array of positive integers. The task is to determine the smallest positive integer that cannot be represented as the sum of a subset of these integers. This is a classic greedy algorithm problem.

For example, if the given array is [1, 2, 3, 10, 20], then the smallest integer that cannot be represented as the sum of some subset of the array is 7.

The input begins with an integer T that represents the number of test cases. Each test case is presented in a single line. The first number in the line is n, the number of elements in the array, followed by n positive integers. For each test case, output the required smallest positive integer on a new line.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
n1 a1 a2 ... an1
n2 b1 b2 ... bn2
...

Where T is the number of test cases. For each test case, the first integer is n (the number of elements in the array) and the next n integers are the positive integers in the array.

outputFormat

For each test case, print a single line to standard output (stdout) containing the smallest positive integer that cannot be represented as the sum of a subset of the given integers.

1
5 1 2 3 10 20

7