Minimum Absolute Difference Partition

You are given an array of integers. Your task is to partition the array into two non-empty subsets such that the absolute difference between the sums of the two subsets is minimized. Note that each integer from the array must belong to exactly one of the two subsets.

For an array \(A\) with total sum \(S\), if one subset has a sum \(X\), then the other subset will have a sum \(S-X\) and the absolute difference is \(|S-2X|\). You need to choose a proper subset (i.e. neither the empty set nor the complete set) so that \(|S-2X|\) is minimized.

Input Example: For the array [1, 2, 3, 4, 5], one optimal partition is {1, 4, 5} and {2, 3}, giving sums of 10 and 5 respectively, and the absolute difference is 5; however, the minimum absolute difference achievable is 1.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each test case is described as follows:

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

You can assume that \(n \ge 2\) because both subsets must be non-empty.

outputFormat

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

## sample

4
5
1 2 3 4 5
6
2 -1 2 -3 4 1
6
1 1 1 1 1 1
5
3 1 4 2 2

1
1
0
0

</p>