# 序列取数

## 题目描述

给定一个长为 $n$ 的整数序列 $(n \le 1000)$，由 A 和 B 轮流取数（A 先取）。每个人可从序列的左端或右端取若干个数（至少一个），但不能两端都取。所有数都被取走后，两人分别统计所取数的和作为各自的得分。假设 A 和 B 都足够聪明，都使自己得分尽量高，求 A 的最终得分。

## 输入格式

第一行，一个正整数 $T$，表示有 $T$ 组数据。（$T \le 100$）

接着 $T$ 行，每行第一个数为 $n$，接着 $n$ 个整数表示给定的序列。

## 输出格式

输出T行，每行一个整数，表示 A 的得分。

## 样例 #1

### 样例输入 #1

```
2
1 -1
2 1 2
```

### 样例输出 #1

```
-1
3
```