题目描述

Jerry 准备偷吃 Tom 的奶酪。所有的奶酪排成了一条直线，每块奶酪都有不同的美味程度。然而，如果有相邻两块奶酪都被 Jerry 偷吃，Tom 就会发现这一点并迅速抓住 Jerry。Jerry 当然希望在不被 Tom 发现的条件下吃到的奶酪美味度总和最大。当然，他也可以选择一块奶酪都不吃。请你帮助他规划一下偷吃的方案，告诉他最多能偷吃到多少的美味度吧。

输入格式

第一行一个整数 $T\ (T\le 100)$，表示测试数据组数。

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

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

输出格式

对于每组测试数据，输出一个整数，表示 Jerry 可以吃到的最大美味度总和。请注意，美味度总和可能超过 int 存储范围。

4
3
1 8 2
4
10 7 6 14
4
1 2 3 1
5
2 7 9 3 1

8
24
4
12

对于第一组样例，阿福选择第 $2$ 家店铺行窃，获得的现金数量为 $8$。

对于第二组样例，阿福选择第 $1$ 和 $4$ 家店铺行窃，获得的现金数量为 $10 + 14 = 24$。