小苯的数字染色

题号：NC297137
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯有 $n$ 个数字，初始均为白色，他可以染红一些数字得到一些分数，具体的，小苯可以做任意次以下操作：
$\hspace{15pt}\bullet$ 选择一个区间 $l, r\ (1 \leqq l \lt r \leqq n)$ ，满足区间端点的数字奇偶性相同，且区间中（包括端点）的所有数字均为白色。将这段区间的所有数字染红，得分为： $a_l+a_r$ 。
$\hspace{15pt}$ 小苯想知道自己最多可以获得多少分，请你帮他算一算吧。

$\hspace{15pt}$ 特别的，如果一次操作都不做则得分为 $0$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行一个正整数 ，表示数字的个数。
第二行  个整数 ，表示每个数字的值。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据：
在单独的一行输出一个整数，表示可以得到的最大得分。

示例1

输入

复制

3
6
1 3 -5 2 -4 4
6
-1 3 5 -2 4 -4
3
-1 -1 100

输出

复制

10
10
0

说明

对于第一组测试数据，选择  染红，得到  分。

再选择  染红，得到  分，总分为  分。