Minimum Difference Partition

You are given a set of stones, each with a positive integer weight. Your task is to partition these stones into two groups such that the absolute difference between the sum of weights of the two groups is minimized.

Let the total weight be \(S\) and one group have a sum of \(S_1\); then the difference is \(|S - 2S_1|\). Find the partition that minimizes this difference.

inputFormat

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

• An integer \(N\) on its own line indicating the number of stones.
• A line with \(N\) space-separated integers denoting the weights of the stones.

outputFormat

For each test case, output a single integer on a new line representing the minimum possible difference between the sum of weights of the two partitions.

2
4
1 6 5 11
3
1 2 3

1
0