Minimum Partition Difference

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

Formally, given an array \(a_1, a_2, \dots, a_n\), find a subset \(S\) such that the expression \(|\text{total} - 2\cdot\text{sum}(S)|\) is minimized, where \(\text{total} = \sum_{i=1}^{n} a_i\) and \(\text{sum}(S)\) is the sum of the subset.

You are required to implement a solution that reads input from stdin and writes the result to stdout for each test case.

inputFormat

The input begins with a single integer \(T\) denoting the number of test cases. Each test case consists of two lines:

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

outputFormat

For each test case, output a single line containing one integer — the minimum absolute difference between the sums of the two partitions.

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

1
0
0