1465 : Select

    Reverie有一个长度为 n 的正整数数组 A, 她想从中挑出一些数字，使得这些数字的和最大，选中的任意两个数字在原数组中不能相邻。
    你能帮帮她么？

第一行一个正整数 T, 代表测试的组数。
每组测试第一行一个正整数 n 表示数组的大小，第二行 n 个正整数表示数组里的数，以空格分隔。
$1 \leq T\leq 100$
$1 \leq n \leq 1000$
$1 \leq A_i \leq 1000$

每组测试，一行内输出一个整数表示选出的数的和。

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

4
12