gems gems gems

Now there are $n$ gems, each of which has its own value. Alice and Bob play a game with these $n$ gems.
They place the gems in a row and decide to take turns to take gems from left to right.
Alice goes first and takes 1 or 2 gems from the left. After that, on each turn a player can take $k$ or $k+1$ gems if the other player takes $k$ gems in the previous turn. The game ends when there are no gems left or the current player can't take $k$ or $k+1$ gems.
Your task is to determine the difference between the total value of gems Alice took and Bob took. Assume both players play optimally. Alice wants to maximize the difference while Bob wants to minimize it.

The first line contains an integer $T$ ($1\leq T \leq 10$), the number of the test cases.
For each test case:
the first line contains a numbers $n$ ($1\leq n \leq 20000$);
the second line contains n numbers: $V_1, V_2\dots V_n$. ($-100000\leq V_i \leq 100000$)

For each test case, print a single number in a line: the difference between the total value of gems Alice took and the total value of gems Bob took.

1
3
1 3 2

4

2017 ACM/ICPC Asia Regional Shenyang Online