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 ≤ 103), where n is the number of boxes in the line.
The second line of each test case contains n integers a1, a2, ..., an ( - 103 ≤ ai ≤ 103), giving the values of the cards inside the boxes.
For each test case, print a single line containing its answer.
## Input
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 ≤ 103), where n is the number of boxes in the line.The second line of each test case contains n integers a1, a2, ..., an ( - 103 ≤ ai ≤ 103), giving the values of the cards inside the boxes.
## Output
For each test case, print a single line containing its answer.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
Let $ S = \{(n_k, A_k) \mid k \in \{1, \dots, T\}\} $ be the set of test cases, where for each $ k $:
- $ n_k \in \mathbb{Z} $ denotes the number of boxes.
- $ A_k = (a_{k,1}, a_{k,2}, \dots, a_{k,n_k}) $ is a sequence of integers representing card values.
**Constraints**
1. $ 1 \le T \le 500 $
2. For each $ k \in \{1, \dots, T\} $:
- $ 1 \le n_k \le 10^3 $
- $ -10^3 \le a_{k,i} \le 10^3 $ for all $ i \in \{1, \dots, n_k\} $
**Objective**
For each test case $ k $, let $ x_k $ be Ibraheem’s final score and $ y_k $ be Husam’s final score, under optimal play (Ibraheem moves first). Compute:
$$
x_k - y_k
$$