Optimal Card Game Strategy

In this problem, two players are playing a card game. A sequence of cards is laid out in a row. Each card has an integer value. The players alternately pick a card from either the leftmost or rightmost end of the row. Both players play optimally in order to maximize their own sum. Your task is to compute the maximum sum that the first player can achieve by the end of the game.

Let \(cards = [a_0, a_1, \dots, a_{n-1}]\) be the array of card values, and let \(dp[i][j]\) denote the maximum net advantage (difference in score) the current player can achieve over the other player from the subarray \(a_i\) to \(a_j\) (inclusive). The recurrence is: \[ \begin{aligned} dp[i][j] = \max( & a_i - dp[i+1][j],\\ & a_j - dp[i][j-1] ) \end{aligned} \]

The total sum of the cards is (S = \sum_{i=0}^{n-1} a_i). The first player's maximum sum is derived from the formula: [ \text{FirstPlayerSum} = \frac{S + dp[0][n-1]}{2} ]

Implement an efficient algorithm that computes this maximum sum given the list of card values for multiple test cases.

inputFormat

The input is given via standard input (stdin) and consists of multiple test cases. The format is as follows:

• The first line contains an integer \(T\) representing the number of test cases.
• For each test case, the first line contains an integer \(n\), the number of cards.
• The next line contains \(n\) space-separated integers representing the values on the cards.

outputFormat

For each test case, output a single line containing the maximum sum the first player can collect when both players play optimally. All outputs should be printed to standard output (stdout).

## sample

5
4
1 2 9 4
3
6 2 3
1
5
6
1 2 3 4 5 6
4
8 15 3 7

10
8
5
12
22

</p>