Optimal Strategy Game

In this problem, two players take turns removing an element from either end of a row of numbers. Both players play optimally, and your task is to determine the maximum possible sum that the first player can collect. Let \(S\) be the sum of all numbers and \(D\) be the difference computed via a dynamic programming recurrence, then the first player's maximum sum is given by

[ \text{First Player Sum} = \frac{S + D}{2} ]

The dynamic programming recurrence is defined as follows:

[ \text{dp}[i][j] = \max\Big( a_i - \text{dp}[i+1][j],\ a_j - \text{dp}[i][j-1] \Big) \quad \text{for } i < j, ]

with the base condition \(\text{dp}[i][i] = a_i\). Use this approach to compute the first player's maximum sum for every test case.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \(T\) representing the number of test cases.
• Each of the following \(T\) lines begins with an integer \(n\), the number of elements in the array, followed by \(n\) space-separated integers representing the values.

outputFormat

For each test case, output the maximum sum that the first player can obtain if both players play optimally. The output for each test case should be printed on a new line to stdout.

## sample

2
4 1 2 9 4
3 4 4 5

10
9

</p>