Partition Array with Minimum Difference

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

Formally, let \(S\) be the set of indices of the array. Partition \(S\) into two disjoint subsets \(S_1\) and \(S_2\) such that the value \[ \left|\sum_{i \in S_1} a_i - \sum_{i \in S_2} a_i\right| \] is minimized. You are required to output this minimum absolute difference.

Hint: Consider using dynamic programming to solve the subset sum problem up to \(\lfloor \frac{\text{total sum}}{2} \rfloor\) and then deduce the answer.

inputFormat

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

• The first line contains an integer n, representing the number of elements in the array.
• The second line contains n space-separated integers, which are the elements of the array.

outputFormat

For each test case, output one integer on a new line representing the minimum absolute difference obtained by partitioning the array into two subsets.

## sample

1
4
1 2 3 4

0

</p>