Description

Given an integer sequence of length $n$ $(n \le 1000)$, A and B take numbers in turns (A goes first). On each turn, a player may take one or more numbers from either the left end or the right end of the sequence, but not from both ends in the same turn. After all numbers have been taken, each player sums the numbers they took as their score. Assume A and B are both clever enough to play optimally and maximize their own score. Find A's final score.

Input Format

The first line contains a positive integer $T$, indicating there are $T$ testcases $(T \le 100)$. Then follow $T$ lines. In each line, the first number is $n$, followed by $n$ integers that form the given sequence.

Output Format

Output $T$ lines, each containing one integer, which is A's score.

2
1 -1
2 1 2

-1
3

Hint

Translated by ChatGPT 5