题目描述
舞台上一排 $N$ 盏艺术灯，第 $i$ 盏的亮度为 $a_i$。灯光师要选一些灯点亮，但相邻两盏不能同时点亮（电路限制）。选中的灯亮度之和越大，演出效果越好。
请求出：在满足限制的前提下，点亮的灯亮度之和最大是多少。共有 $T$ 组舞台布景要分别计算。
输入格式
第一行一个整数 $T$，表示布景组数。 每组数据两行：第一行一个整数 $N$；第二行 $N$ 个正整数 $a_1, a_2, \cdots, a_N$，用空格分隔。
输出格式
$T$ 行，每行一个整数：该组布景能得到的最大亮度总和。
数据范围
$$1 \le T \le 50,\quad 1 \le N \le 5000,\quad 1 \le a_i \le 1000$$