Description

There are $n$ coins, which may have different values. The value of the $i$-th coin is $v_i$.

Now we need to split them into two parts such that the difference in the numbers of coins does not exceed $1$. What is the minimum possible difference between the total values of the two parts?

Input Format

This problem contains multiple sets of testdata within a single test point.

The first line contains a positive integer $T$, denoting the number of test cases in this test point.

For each test case:

Each test case consists of two lines.

The first line contains an integer $n$, denoting the number of coins.

The second line contains $n$ integers. The $i$-th integer denotes the value $v_i$ of the $i$-th coin.

Output Format

For each test case, output one line with a single integer denoting the answer.

2
3
2 2 4
4
1 2 3 6

0
2

Hint

Constraints

• For $30\%$ of the data, it is guaranteed that $1 \leq v_i \leq 1000$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq T \leq 20$, $1 \leq n \leq 30$, $1 \leq v_i \leq 2^{30}$.

Translated by ChatGPT 5