Minimizing Task Assignment Difference

You are given T test cases. In each test case, there are N tasks, each with an associated difficulty level. Your goal is to assign these tasks to two persons such that the absolute difference between the sum of difficulty levels assigned to each person is minimized.

Formally, let the tasks be represented by an array \(a_1, a_2, \dots, a_N\). You need to partition the array into two subsets \(S_1\) and \(S_2\) such that the value \(|\sum_{x\in S_1} x - \sum_{x\in S_2} x|\) is as small as possible.

Note: There is at least one test case, and for each test case the answer is the minimum possible difference achievable.

inputFormat

The input is given via standard input in the following format:

T
N₁
a₁ a₂ ... aₙ₁
N₂
a₁ a₂ ... aₙ₂
...
Nₜ
a₁ a₂ ... aₙₜ

Where T is the number of test cases, Nᵢ is the number of tasks in the i-th test case, and the following line for each test case contains Nᵢ integers representing the difficulty levels of the tasks.

outputFormat

For each test case, output a single line containing the minimum absolute difference between the sums of difficulties of the two persons.

## sample

2
3
1 2 3
4
1 2 3 4

0
0

</p>