Team Partition Problem

You are given an even number N representing the number of participants and a list of N integer scores. Your task is to divide the participants into two teams with exactly N/2 members each, such that the absolute difference between the sum of the scores of the two teams is minimized.

Mathematically, if the scores are given in the set \(S\) and you choose a subset \(A\subset S\) of exactly \(\frac{N}{2}\) elements, you need to minimize the following expression:

[ \left| \sum_{a \in A} a - \Bigl(\sum_{s \in S} s - \sum_{a \in A} a\Bigr) \right| ]

It is guaranteed that N is even and small enough to allow an exhaustive search.

inputFormat

The first line of input contains an integer T (the number of test cases). For each test case, the first line contains an even integer N representing the number of participants. The following line contains N space-separated integers, representing the scores of the participants.

outputFormat

For each test case, output a single line containing the minimal absolute difference between the sums of the scores of the two teams.## sample

1
4
1 6 11 5

1