Cookies

Time limit2sMemory limit128 MB

Summary

Both players take the best remaining cookie in turn with Zbyszek starting, and you add at most one cookie of any quality to minimize his total minus Hektor's.

Level: Medium6 of 10
Topics: Sorting, Prefix sum, Greedy
Solved: No attempts yet

Problem

Hektor and Zbyszek go out for cookies every morning. Each time, the baker prepares $N$ cookies, and every cookie is labeled with a single natural number describing its quality. The two boys take turns picking one cookie at a time, and each of them always takes the best cookie among those still available.

This week it is Zbyszek's turn to pick first, which Hektor finds very unfair. Hektor wants Zbyszek's advantage, defined as (the total quality of the cookies Zbyszek picks) minus (the total quality of the cookies Hektor picks), to be as small as possible. To achieve this, he decides to use a little trick.

Early in the morning, Hektor calls the baker, who is just finishing work, and asks about today's cookies. The baker is very fond of Hektor, so at his request the baker can add to the batch one extra cookie of any quality that Hektor chooses.

Given the qualities of the prepared cookies, and being allowed to add at most one extra cookie of any natural-number quality, compute the smallest advantage of Zbyszek over Hektor that Hektor can achieve.

Input

The first line contains the number of test cases $Z$ ( $1 \le Z \le 10$ ). The $Z$ test cases follow.

Each test case begins with a natural number $N$ ( $1 \le N \le 1\,000\,000$ ), the number of cookies the baker prepared.

The next line contains $N$ natural numbers $A_i$ ( $1 \le A_i \le 1000$ ), the qualities of the successive cookies.

Output

For each test case, print on its own line the minimum possible difference between the total quality of Zbyszek's cookies and the total quality of Hektor's cookies.

Examples3

Example 1

Input

4 
2 
1 1 
2 
1 2 
3 
1 1 1 
5 
16 15 7 8 3

Expected output

Example 2
Input
```
1
1
1
```
Expected output
```
0
```
Example 3
Input
```
1
6
1 2 3 4 5 6
```
Expected output
```
3
```