题目描述

$\text{Jerry}$准备偷吃$\text{Tom}$的奶酪。所有的奶酪排成了一条直线，每块奶酪都有不同的美味程度。然而，如果有相邻两块奶酪都被$\text{Jerry}$偷吃，$\text{Tom}$就会发现这一点并迅速抓住$\text{Jerry}$。

$\text{Jerry}$当然希望在不被$\text{Tom}$发现的条件下吃到的奶酪美味度总和最大。当然，他也可以选择一块奶酪都不吃。请你帮助他规划一下偷吃的方案，告诉他最多能偷吃到多少的美味度吧。

输入

第一行一个整数$T$ ($T\leq100$)，表示测试数据组数。 接下来，每组测试数据包含两行。其中，第一行一个整数n ($1 \leq n \leq 100,000$) ，表示奶酪的数量；

第二行$n$个整数，表示这一排直线上奶酪的美味程度，请注意，美味度保证能够被$\text{int}$类型存储，且可能是负数。

输出

对于每组测试数据，输出一个整数，表示$\text{Jerry}$可以吃到的最大美味度总和。

请注意，美味度总和可能超过$\text{int}$存储范围

2
4
1 2 3 1
5
2 7 9 3 1

4
12