g6-07917. 打家劫舍·多测 未做

有 $T$ 组数据。每组数据是一条街上的 $n$ 间房，第 $i$ 间房里有 $a_i$ 元现金，小偷不能偷相邻的两间房。对每组数据求最多能偷到多少钱。

第一行一个整数 $T$（$1\le T\le 10$）。

接下来 $T$ 组，每组两行：第一行 $n$，第二行 $n$ 个整数 $a_1,\dots ,a_n$。

$T$ 行，每行一个整数，表示该组数据的最大金额。

输入 1

2
5
2 7 9 3 1
3
2 3 2

输出 1

12
4

对于所有数据，$1\le T\le 10$，$1\le n\le 10^5$，$1\le a_i\le 10^4$，所有组 $n$ 之和不超过 $10^5$。