Optimal Coin Game

You are given a row of n coins, where each coin has a positive integer value. Two players take turns picking a coin from either end of the row. Both players play optimally to maximize the total value they can accumulate. Your task is to determine the maximum total value that the starting player can secure.

The game is modeled using optimal strategy, and the solution involves dynamic programming. In particular, define a DP table \(dp[i][j]\) which represents the maximum value the current player can achieve from coins \(i\) to \(j\) (inclusive). The recurrence involves considering the opponent's optimal play, and is given by:

[ dp[i][j] = \max\left( coins[i] + \min\left( dp[i+2][j],, dp[i+1][j-1] \right), ; coins[j] + \min\left( dp[i+1][j-1],, dp[i][j-2] \right) \right) ]

with the appropriate base cases.

inputFormat

The first line contains an integer t representing the number of test cases. Each test case is described as follows:

• The first line of each test case contains an integer n, the number of coins.
• The next line contains n space-separated integers representing the coin values.

Input is read from standard input (stdin).

outputFormat

For each test case, print a single integer representing the maximum value the starting player can obtain if both players play optimally.

Output should be sent to standard output (stdout), with each test case's result on a new line.

## sample

2
4
1 2 3 4
4
4 3 2 1

6
6

</p>