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}。

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

数据范围

对于 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。