No submission language available for this problem.

Background

Special for beginners, ^_^

Description

现在有一个 n 个元素的数组 a[1...n]，需要你去找到一种特别的非空子串数组。该数组将会有一种要求，相邻之间的数，不能够是同一种奇偶性。

举个例子，{1，2，3} 是可以接受的；但 {1，2，4} 不能被接受，因为 2 和 4 都是偶数，且相邻。

你需要找到一个这样的子串数组，且是总和最大。

Format

Input

多组测试

第一行一个整数 t（1<=t<=$10^4$）表示有 t 组测试

每组测试第一行一个整数 n (1 <= n <= 2*$10^5$) 表示改组序列有 n 个整数。

每组测试第二行有 n 个整数，$a_1,a_2,...a_n$ ($-10^3 \leq a_i \leq 10^3$)

Output

数组有 t 组，每组一个答案表示该组序列中，符合要求的子串数组的总和最大值。

Samples

7
5
1 2 3 4 5
4
9 9 8 8
6
-1 4 -1 0 5 -4
4
-1 2 4 -3
1
-1000
3
101 -99 101
20
-10 5 -8 10 6 -10 7 9 -2 -6 7 2 -4 6 -1 7 -6 -7 4 1

15
17
8
4
-1000
101
10

Limitation

1s, 1024KiB for each test case.