Minimum Absolute Difference Partition

You are given a set of items with integer weights. Your task is to partition these items into two groups such that the absolute difference between the sum of the weights in the two groups is minimized. Formally, if (S) is the total sum of all items and (P) is the sum of one group, you must minimize the value of (|S - 2P|).

For example, if the weights are [1, 6, 11, 5], one optimal partition is [1, 5, 6] and [11] with a minimum difference of 1. Solve the problem for multiple test cases. All input should be read from standard input (stdin) and all output should be written to standard output (stdout).

inputFormat

The first line of input contains an integer (T) denoting the number of test cases. For each test case:

• The first line contains an integer (n) — the number of items.
  
• The second line contains (n) space-separated integers representing the weights of the items.

outputFormat

For each test case, output a single integer — the minimum possible absolute difference between the sums of the two groups. Each answer should be printed on a new line.## sample

3
4
1 6 11 5
3
1 2 3
5
10 20 30 40 50

1
0
10