题目描述

给定一个长为 $n$ 的整数序列 $(n \le 1000)$，由 A 和 B 轮流取数（A 先取）。每个人可从序列的左端或右端取若干个数（至少一个），但不能两端都取。所有数都被取走后，两人分别统计所取数的和作为各自的得分。假设 A 和 B 都足够聪明，都使自己得分尽量高，求 A 的最终得分。

输入格式

第一行，一个正整数 $T$，表示有 $T$ 组数据。（$T \le 100$）

接着 $T$ 行，每行第一个数为 $n$，接着 $n$ 个整数表示给定的序列。

输出格式

输出T行，每行一个整数，表示 A 的得分。

2
1 -1
2 1 2

-1
3