Minimum Subset Sum Difference Partition

Given a set of integers, your task is to partition the set into two subsets such that the absolute difference between the sums of the two subsets is minimized.

Formally, given a set \(A = \{a_1, a_2, \dots, a_n\}\), find two disjoint subsets \(S_1\) and \(S_2\) such that \(S_1 \cup S_2 = A\) and \(S_1 \cap S_2 = \emptyset\) and minimize the value

$$|\sum_{i \in S_1}a_i - \sum_{j \in S_2}a_j|.$$

Output the minimum absolute difference achievable.

inputFormat

The input begins with an integer t on the first line indicating the number of test cases.

Each test case consists of two lines:

• The first line contains an integer n, the number of elements in the set.
• The second line contains n space-separated integers representing the elements of the set.

You should read input from stdin.

outputFormat

For each test case, output a single line containing the minimum absolute difference between the sums of the two subsets.

The results should be written to stdout.

## sample

3
5
1 2 3 4 5
3
8 6 4
4
1 2 3 9

1
2
3

</p>