Minimum Partition Difference

You are given an array of N integers. Your task is to split the array into two non-empty parts such that the absolute difference between the sums of the two parts is minimized.

Formally, let the array be \(a_1, a_2, \dots, a_N\). You need to partition the array into two parts \(P\) and \(Q\) (both non-empty) so that the value \[ \left| \sum_{x \in P} x - \sum_{x \in Q} x \right| \] is minimized. This is equivalent to finding a subset of elements with sum \(S\) as close as possible to \(\frac{\text{total sum}}{2}\), where the total sum is \(\sum_{i=1}^{N} a_i\).

Input Constraints: The number of elements N is at least 2, and the elements are positive integers.

Example:

Input:
5
1 2 3 4 5

Output:
1

In the above example, splitting the array into [1, 2, 3, 4] and [5] gives sums 10 and 5 respectively, resulting in a difference of 5; however, the optimal split is [1, 2, 3, 5] and [4] with sums 11 and 4 respectively, yielding a minimal difference of 7, so a better partition is found resulting in the minimum difference of 1.

Your solution should read input from stdin and write the result for each test case to stdout.

inputFormat

The first line contains an integer T representing the number of test cases. For each test case:

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

outputFormat

For each test case, output a single line containing the minimum absolute difference between the sums of the two parts after an optimal partition.## sample

3
5
1 2 3 4 5
4
8 15 7 3
2
1 2

1
3
1