Maximum Score Game

You are given an array of integers representing scores. Two players alternately choose a number from either end of the array. Both players play optimally and try to maximize their total score. Your task is to compute the maximum score the first player can obtain.

The game is as follows:

• At each turn, a player may remove either the leftmost or rightmost number from the array.
• The removed number is added to the player's total score.
• Both players play optimally.

Formally, let \(a_0, a_1, \ldots, a_{n-1}\) be the array. The solution can be derived using a dynamic programming approach with the recurrence \[ \mathrm{dp}[i][j] = \max \Bigl(a_i + \min(\mathrm{dp}[i+2][j],\, \mathrm{dp}[i+1][j-1]),\, a_j + \min(\mathrm{dp}[i+1][j-1],\, \mathrm{dp}[i][j-2])\Bigr) \] for \(0 \le i \le j \le n-1\) with appropriate base cases.

inputFormat

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

• The first line contains a single integer \(T\) representing the number of test cases.
• For each test case, the first line contains an integer \(N\) representing the number of coins.
• The second line contains \(N\) space-separated integers, which are the values of the coins.

outputFormat

For each test case, output a single line to standard output (stdout) containing the maximum score the first player can achieve.

## sample

5
4
8 15 3 7
4
20 30 2 2
5
1 2 3 4 5
3
9 10 11
1
10

22
32
9
20
10

</p>