Unique Subset Sums

Given a set of coins with positive integer weights, your task is to determine the number of unique sums that can be formed by selecting any subset of these coins. Note that the empty subset is also considered, and by definition there are \(2^n\) possible subsets if there are \(n\) coins.

For each test case, you will be provided with the number of coins and their corresponding weights. The goal is to compute the number of distinct subset sums obtainable, including the sum of 0 (from the empty subset). For example, if the coins are [1, 2, 3], then the unique sums are \(\{0, 1, 2, 3, 4, 5, 6\}\) and the expected output is 7.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) representing the number of test cases. Each of the following (T) lines represents a test case and contains the following:

n a1 a2 ... an

where (n) is the number of coins and (a1, a2, ..., an) are the weights of the coins.

outputFormat

For each test case, output a single line to standard output (stdout) containing one integer: the number of unique subset sums that can be formed.## sample

3
3 1 2 3
2 1 5
4 3 3 3 3

7
4
5