Rajkumar and Chitra are good friends. They have decided that they will study DAA (Design and Analysis of Algorithms) together. After some days they found a very interesting problem in the book. They are trying to solve the problem. Can you help them?

Given N numbers. You can do two operations on the set of numbers.

1. Reverse the sign of any number X in the set. (X = -X)
2. Divide the set in two parts (not necessarily equal sized) such that the difference between the sum of the two parts is closest to zero. The two parts doesn't need to be contiguous array elements. The difference must be non-negative. You can also pick no number in one part and all in the other.

You can perform the reverse sign operation any number of times.

You have to find the minimum possible difference that you can get from second operation.

For example, array [2, -1, -3, 3]. After doing 2 reverse operations we can get [-2, -1, -3, -3]. Applying second operation this set can be broken into two parts [-2, -3] and [-1, -3] with the difference in sums = (-4) - (-5) = 1. You can not find any difference less than 1.

Input

The first input line contains integer T (T <= 100) which represents the number of test cases. In first line of every test case we have number of numbers N [1 <= N <= 100]. In the next line there are N numbers A1 A2 ... AN [-100 <= Ai <= 100].

Output

Print the desired answer for each test case in newline.

Example

Input:
2
4
2 -1 -3 3
4
1 -1 2 -2

Output:
1
0