Optimal Strategy for a Coin Game

You and your friend Ninjax are engaged in a strategic game involving coins. Ninjax arranges 'N' coins in a linear sequence.

The rules of the game are as follows:

1. Each coin has an associated value. 2. Two players, including yourself and your opponent, take alternating turns. 3. On their turn, a player can choose either the first or last coin in the remaining sequence and remove it from play. 4. The value of the chosen coin is added to the player's total winnings. 

Your friend Ninjax allows you to take the first turn.

Your goal is to determine the maximum amount you can be guaranteed to win by the end of the game, assuming Ninjax plays optimally.

Input:

The input begins with an integer T, representing the number of test cases. For each test case, the first line contains an integer 'N' indicating the number of coins. The second line provides 'N' space-separated integers, each denoting the value of the coins.

Output:

For each test case, output the maximum amount you can win, printed on a new line.

Example:

Input:

2 4 9 5 21 7 4 20 50 5 10

Output:

30 60

Explanation:

For the first test case, selecting coins in the order of 9 and 21 ensures you a maximum win of 30. In the second test case, choosing 10 and 50 results in a 60 total win.

Constraints:

• 1 ≤ 'T' ≤ 10
• 2 ≤ 'N' ≤ 10³
• 0 ≤ 'VALUE' ≤ 10⁵
• 'N' is always an even number.

Note: Optimal play by Ninjax means he will always aim to maximize his total win.