404418: GYM101502 J Boxes Game

Ibraheem and Husam are playing a game with group of boxes, lined next to each other on a straight line, such that each box contains a card with some value written on it. Ibraheem and Husam already know the values of all cards before the game starts.

Ibraheem and Husam take turns to play the game, Ibraheem starts first. In each turn, a player can take one box from either ends of the line, add the value of the card inside this box to his score, then remove this box from the line.

Knowing that both players play optimally, your task is to calculate the value x - y, such that x is Ibraheem's score at the end of the game, and y is Husam's score at the end of the game.

The first line contains an integer T (1 ≤ T ≤ 500), where T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 10³), where n is the number of boxes in the line.

The second line of each test case contains n integers a₁, a₂, ..., a_n ( - 10³ ≤ a_i ≤ 10³), giving the values of the cards inside the boxes.

For each test case, print a single line containing its answer.

5
4
3 1 100 5
1
1000
4
-1 100 4 -5
1
-4
1
0

97
1000
92
-4
0