Given a set of n integers denoting the strength of each student participating in a tug of war, divide the students into 2 equal parts such that the difference between the strengths of both the groups is minimum. Return the difference between the strengths of both the groups.

Note: If the number of students is odd, one group will have an extra student.

Examples

strengths: [1, 2, 3, 4]
group 1: [1, 4]
group 2: [2, 3]
difference: 0

strengths: [5, 1, 2, 8]
group 1: [1, 8]
group 2: [2, 5]
difference: 2

strengths: [1, 2, 3, 4, 5]
group 1: [1, 2, 5]
group 2: [3, 4]
difference: 1

Testing

Input Format

The first line contains an integer ‘T’, denoting the number of test cases.

For each test case, the input has two lines.

• An integer ‘n’ denoting the length of the array strengths.
• n space-separated unique integers denoting the elements of the array strengths.

Output Format

For each test case, the output contains the min difference in strengths of the two groups.

Sample Input

3
4
1 2 3 4
4
5 1 2 8
5
1 2 3 4 5

Expected Output

0
2
1

Constraint

1 <= T <= 10

1 <= n <= 20

1 <= Ai <= 500