Minimum Difference Partition

Given a list of project completion times, your task is to partition the projects into two groups such that the absolute difference between the sum of their completion times is minimized.

This problem can be formulated as follows: Let \( S \) be the total sum of completion times, and let \( S_1 \) and \( S_2 \) be the sums of the two groups such that \( S_1 + S_2 = S \). The goal is to minimize the absolute difference \( |S_1 - S_2| \). This is a classic variation of the Partition Problem (or subset-sum problem) using dynamic programming.

The input contains multiple test cases. For each test case, determine the minimum possible difference between the two groups.

inputFormat

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

• The first line contains a single integer \( N \) — the number of projects.
• The second line contains \( N \) space-separated positive integers representing the project completion times.

All input should be read from standard input (stdin).

outputFormat

For each test case, output a single line with one integer representing the minimum possible difference between the total completion times of the two groups.

All output should be written to standard output (stdout).

## sample

3
3
3 1 4
4
2 3 5 10
4
1 2 3 9

0
0
3

</p>