Victory at all costs, victory in spite of all terror, victory however long and hard the road may be; for without victory, there is no survival.
-Winston Churchill

Inspired by this quote, the students of NSIT plan on attacking the alien warship and putting an end to the oppression, once and for all.

The plan is to attack the aliens from both flanks and kill em all. Two teams are going to be made for this task. The leader of our forces, Ayush, wants the two attack parties led by Arpit and Gaurav to be of similar strengths.

Input

First line of input will contain an integer t, the number of test cases. For each test case first line gives an integer n, the size of the total army, following n lines will contain the strength of each student.

Output

You have to print the absolute difference in strengths of the most optimum division of each set into 2 subsets.

Constraints

1 <= t <= 50

0 < Total number of students <= 500

0 < strength <= 500

Example

Input:
2
5
13
53
19
397
181
8
41
43
47
79
83
443
167
239

Output:
131
4