Cookies

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.

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.

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.