Minimum Team Skill Difference

In this problem, you are given the skills of players and you need to partition them into two teams such that the absolute difference between the total skill levels of the two teams is minimized. Formally, for a set of players with skill levels (a_1, a_2, \dots, a_n), let the total sum be (S = \sum_{i=1}^n a_i). If you choose a subset with sum (s), the difference will be (|S - 2s|). Your task is to determine the minimum possible difference. It is guaranteed that the number of players in each test case is small enough to allow a brute force solution using subset enumeration.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) representing the number of test cases. Each test case is described by two lines. The first line of each test case contains an integer (n) indicating the number of players. The second line contains (n) space-separated integers representing the skill levels of the players.

outputFormat

For each test case, output a single line containing the minimum absolute difference between the total skill levels of the two teams. All outputs are printed to standard output (stdout).## sample

3
4
1 2 3 4
3
10 20 15
5
2 2 2 2 2

0
5
2