Minimum Absolute Difference Partition

You are given an array of positive integers. Your task is to partition the array into two parts such that the absolute difference of the sums of the two parts is minimized. Formally, if one part has a sum \(S_1\) and the other part has a sum \(S_2\), you need to minimize \(|S_1 - S_2|\). This problem can be solved using a dynamic programming approach similar to the subset sum problem.

Example:

• For the array [1, 2, 3, 4, 5], one optimal partition is [1, 4, 5] and [2, 3] with sums 10 and 5 respectively, yielding an absolute difference of 5. However, note that the optimal answer for this instance is actually 1 using a proper partitioning strategy involving a subset sum dynamic programming method.
• For the array [1, 1, 1, 1], the array can be partitioned into two parts each having a sum of 2, resulting in a difference of 0.

Input/Output: The program reads from standard input and writes to standard output.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each test case consists of two lines. The first line of a test case contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated positive integers representing the elements of the array.

Example:

3
5
1 2 3 4 5
4
1 1 1 1
3
3 7 2

outputFormat

For each test case, output a single line containing an integer which is the minimum absolute difference between the sums of two parts after partitioning the array.

Example:

1
0
2

## sample

3
5
1 2 3 4 5
4
1 1 1 1
3
3 7 2

1
0
2

</p>