Minimum Subset Sum Difference

You are given a collection of positive integers. Your task is to partition this collection into two subsets such that the absolute difference between the sum of the elements in each subset is minimized.

More formally, given an array \(A = [a_1, a_2, \dots, a_n]\), partition it into two disjoint subsets \(S_1\) and \(S_2\) (\(S_1 \cup S_2 = A\) and \(S_1 \cap S_2 = \emptyset\)) such that the value \(|\sum_{x \in S_1} x - \sum_{x \in S_2} x|\) is minimized. This absolute difference is what you need to compute.

Note: It is possible that one of the subsets is empty. In that case, the difference is simply the sum of all elements.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. For each test case, the input is provided in the following format:

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

All input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the minimum absolute difference between the sums of two subsets, computed according to the specification. All output should be written to standard output (stdout).

## sample

2
4
1 6 11 5
3
1 2 3

1
0

</p>