Minimum Power Difference Partition

You are given several test cases. In each test case, you are provided with an integer n indicating the number of servers and a list of n integers representing the processing power ratings of these servers. Your task is to partition the servers into two groups such that the absolute difference between the total processing power of the groups is minimized.

Note: It might not be possible to split the servers into two groups of equal sum. In that case, output the minimum difference possible.

The problem can be reduced to finding a subset of numbers whose sum is as close as possible to \(\frac{\text{total sum}}{2}\) when compared with the sum of the remaining elements. Use dynamic programming to solve the subset sum problem.

inputFormat

The input is read from stdin and has the following format:

• The first line 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 servers.
• The next line contains \(n\) space-separated integers representing the processing power ratings of the servers.

outputFormat

For each test case, print the minimum possible difference in processing power between the two groups on a separate line to stdout.

## sample

3
2
1 2
4
1 2 3 4
3
2 2 3

1
0
1

</p>