Card Game

Geunwoo and Myungwoo play a card game. $N$ cards lie in a row, and each card has one number written on it. Geunwoo goes first, and the two players alternate turns. On a turn, a player can take either the leftmost card or the rightmost card of the row. The turns repeat until no card is left. Each player's score is the sum of the numbers on the cards that player took.

Both players play the strategy that maximizes their own score. Given the number of cards $N$ and the number on each card, write a program that computes Geunwoo's score.

For example, suppose the cards read 4, 3, 1, 2 from the left. Geunwoo takes 4 and Myungwoo takes 3. Then Geunwoo takes 2 and Myungwoo takes the last card, 1. With both playing their best strategy, Geunwoo's score is 6.

The first line has the number of test cases $T$ ($1 \le T \le 50$).

For each test case, the first line has the number of cards $N$ ($1 \le N \le 1000$). The second line has $N$ natural numbers separated by spaces, where the $i$-th number is written on the $i$-th card from the left. Every number on a card is between $1$ and $10000$.

For each test case, print Geunwoo's score when both players play their best strategy, one score per line.