Time Limit: 1.0 s

Memory Limit: 64.0 MB

Description

Roy and Hridoy play a game on a multiset of N integers on the board. They maintain a running total S, initially 0. Roy moves first and they alternate turns. On each turn the current player may either

• stop the game (only if both players have already made at least one move), fixing the final total S,
• or choose and remove one remaining integer x from the board and update S as follows:
  • on Roy’s turn: S ← S + x
  • on Hridoy’s turn: S ← S – x

Roy aims to maximize the final total S; Hridoy aims to minimize it. Assuming both play optimally, determine the value that Roy can guarantee.

Input

• The first line contains a single integer  \(T\) (\(1 ≤ T ≤ 10^4\)) — the number of test cases.

• Each test case consists of two lines:

  • The first line contains a single integer \(N\) (\(2 ≤ N ≤ 2 * 10^5\))— the number of integers on the board.

  • The second line contains \(N\) integers \(A₁, A₂, …, A_N\) ( \(−10^9 ≤ A_i ≤ 10^9\) ).

• It is guaranteed that sum of \(N\) over all test cases does not exceed \(2 * 10^5\).

Output

• For each test case, print one integer — maximum the final total S that Roy can guarantee under optimal play.

Sample

3
4
3 4 0 -6
2
5 10
5
-4 -6 -2 -2 -2

1
5
0

Test case 1 :
N = 4, Board = {3, 4, 0, -6}, S starts at 0.

1. Roy’s move: he removes 4, S = 0 + 4 = 4. Remaining {3, 0, -6}.

2. Hridoy’s move: he removes 3, S = 4 – 3 = 1. Remaining {0, - 6}.

Now stopping is allowed.

3. Roy can either stop (getting S = 1) or continue. He continues and removes 0, S = 1 + 0 = 1. Remaining {-6}.

4. Hridoy stopping gives S = 1; any further pick would make S lager, so he stops.
   Final answer for this test case: 1

Test case 3 :
N = 5, Board = {-4, -6, -2, -2, -2}, S starts at 0.

1. Roy’s move: he removes -2, S = 0 + (-2) = -2. Remaining {-4, -6, -2, -2}.

2. Hridoy’s move: he removes -2, S = -2 - (-2) = 0. Remaining {-4, -6, -2}.

Now stopping is allowed.

3. Roy can either stop (getting S = 0) or continue. Any further pick would make S smaller, so he stops.

So final S equal to 0.