Minimum Team Skill Difference

You are given an even integer \( n \) representing the number of participants and a list of \( n \) integers where each integer represents the skill level of a participant. Your task is to divide the participants into two teams of equal size (i.e. each team has \( \frac{n}{2} \) participants) such that the absolute difference between the total skill levels of the two teams is minimized.

Let the sum of the skills in one team be \( S_A \) and in the other team be \( S_B \). You need to minimize the value of \( |S_A - S_B| \). If \( T \) is the total sum of skill levels, then note that \( S_B = T - S_A \) and the absolute difference is given by \( |T - 2S_A| \). Your goal is to choose a subset of \( \frac{n}{2} \) participants with a sum \( S_A \) such that \( |T - 2S_A| \) is as small as possible.

It is guaranteed that \( n \) is even.

inputFormat

The input is read from stdin and has the following format:

• The first line contains a single integer \( T \), the number of test cases.
• For each test case, the first line contains an even integer \( n \) (the number of participants).
• The second line contains \( n \) space-separated integers representing the skill levels of the participants.

outputFormat

For each test case, output a single line to stdout containing the minimum possible absolute difference between the sums of the skills of the two teams.

## sample

3
4
10 20 15 25
6
1 6 11 5 10 15
2
1 2

0
4
1

</p>