Minimum Difference Subarray Partition

You are given an array of integers. Your task is to partition the array into two subarrays such that the absolute difference of their sums is minimized.

Let \( S \) be the total sum of the array, and let \( S_1 \) be the sum of the first subarray and \( S_2 \) be the sum of the second subarray. Your goal is to choose a subset such that \( S_1 \) is as close as possible to \( \frac{S}{2} \). The answer is \( |S_1 - S_2| = |S - 2S_1| \).

Note: The input is read from standard input (stdin) and the output is printed to standard output (stdout).

inputFormat

The first line contains an integer \( T \) representing 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 array.
• The second line contains \( N \) space-separated integers representing the elements of the array.

outputFormat

For each test case, output a single integer in a new line representing the minimum absolute difference between the sums of the two subarrays.

## sample

2
4
1 2 3 4
5
5 6 11 3 2

0
1

</p>