Minimum Partition Difference

You are given a list of n positive integers. Your task is to partition the list into two subsets such that the absolute difference between the sum of the elements in the two subsets is minimized. In particular, if the sum of the first subset is S₁ and the sum of the second subset is S₂, then you need to minimize

$$|S_1 - S_2|$$

For example, given the array [1, 6, 11, 5], one optimal partition is [1, 5, 6] and [11] resulting in an absolute difference of 1. Solve the problem for multiple test cases.

inputFormat

The input starts with a single integer T (T > 0) denoting the number of test cases. The description of each test case follows.

For each test case:

• The first line contains an integer N, the number of elements in the array.
• The second line contains N space-separated integers, representing the list of numbers.

You should read the input from stdin.

outputFormat

For each test case, output a single integer on a new line representing the minimum achievable absolute difference between the sums of two subsets.

The output should be written to stdout.

## sample

2
4
1 6 11 5
5
3 1 4 2 2

1
0

</p>