环形取数
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给出一个元素个数为 \text n 的环形序列，其中 a_i,a_{i+1} 相邻，特殊的 a_1,a_n 相邻。

Alice 和 Bob 正在玩一个取数游戏，游戏规则如下：

- Alices 先手，Bob 后手。
- 先手第一次取数可以取走环上的任意一个数。
- 除先手第一次取数外，每次取数只能从上一个人取走的数的左右两边取一个。
- 每取走一个数，剩下的数仍看成一个环。

Alice 的得分为 Alice 取到的数的和，Bob 的得分为 Bob 取到的数的和。

现在假设 Alice 和 Bob 都采取最优策略，那么 Alices 的得分最终会是多少。

输入描述:

第一行一个整数 t(1\le t \le 2500)，代表测试数据组数。

对于每组测试数据：第一行一个整数 n(1\le n \le 5000)，表示元素个数。

第二行 n 个整数：{a_1,a_2,a_3,...,a_i,...,a_n}(1\le a_i \le 10^9 )。

对于同一测试点，保证 \sum n \le 5000。

输出描述:

输出一个整数代表答案。
示例1

输入

复制 
1
5
4 5 2 2 5

输出

复制 
11