题目描述

Carol 有一个条形棋盘，棋盘上依次放置了 $n$ 个棋子，从左到右标号为 $1, 2, \dots, n$，每个棋子上标有一个整数 $a_i$。Carol 可以按照如下规则进行操作来获得得分，初始得分为 $0$。

每次，Carol 可以执行以下三种操作之一：

1. 选择奇数列的棋子：选择棋盘从左往右数第 $i$ 列（即奇数列）的棋子，将该棋子移除并将其值加到当前得分上。
2. 选择偶数列的棋子：选择棋盘从左往右数第 $i$ 列（即偶数列）的棋子，将该棋子移除，但分数不会发生变化。
3. 终止游戏：Carol 可以在任何时刻结束游戏，无需移除棋盘上所有棋子。

每次移除棋子后，棋盘上的其余棋子会重新按从左到右的顺序排列并重新编号。Carol 的目标是通过合理操作，使游戏结束时的得分最大化，请你帮助他求出这个最大得分。

输入格式

第一行一个整数 $T$ 表示数据组数。

对于每组数据：

第一行一个正整数 $n$。

第二行 $n$ 个整数 $a_{1\sim n}$。

输出格式

对于每种数据，输出一行一个整数表示答案。

4
4
-4 1 -3 5
4
1 -2 3 -4
3
-1 3 -5
1
-1

5
4
2
0

数据范围

对于 $30\%$ 的数据，$1\leq n,\sum n\leq 10$。

对于 $60\%$ 的数据，$1\leq n,\sum n\leq 5000$。

对于 $100\%$ 的数据，$1\leq T\leq 10^4$，$1\leq n,\sum n\leq 2\times 10^5$，$-10^9\leq a_i\leq 10^9$。