Minimum Partition Difference

You are given an array of non-negative 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, if the two subsets have sums \(S_1\) and \(S_2\) respectively, you need to minimize \(|S_1-S_2|\). Note that one of the subsets may be empty.

Example: For the array [1, 2, 3, 9], one optimal partition is \([1, 2, 3]\) and \([9]\) with sums 6 and 9 respectively, yielding an absolute difference of 3.

This is essentially a variation of the partition problem and can be solved using dynamic programming techniques.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. Each test case consists of two lines:

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

outputFormat

For each test case, output a single line with the minimum absolute difference between the sums of the two subsets.

## sample

2
4
1 2 3 9
5
1 5 11 5 9

3
1

</p>