题目描述

光头强进入了一个大宝库，里面有许许多多个装着宝藏的房间，第 $i$ 号房间上有一个数字 $a_i$，代表着进入后能获得 $a_i$ 份宝藏，但是光头强一旦进入第 $i$ 号房间，第 $i-1$ 和 第 $i+1$ 号房间的门便会永久关闭。 请你帮光头强设计一个算法，使他能够获得尽可能多的宝藏。 例如，房间上的数字分别为 $(3,2,2,3)$：时，若光头强先进入第 $4$ 号房间获得 $3$ 份宝藏，此时 $3$ 号房间会关闭；然后光头强可选择进入第 $1$ 号房间获得 $3$ 份宝藏，此时 $2$ 号房间会关闭，无房间可进。一共能获得 $6$ 份宝藏。

输入格式

输入数据的第一行是一个整数 $t$，代表测试的组数，接下来 $t$ 行每一行第一个数字 $n$ 代表房间数量，之后的 $n$ 个数 $a_i$ 分别代表第 $i$ 个房间内的宝藏数量。$(1\leq t \leq 100, 1\leq n \leq 1000, 1\leq a_i \leq 10^6)$

输出格式

对于每组数据，输出一个整数，表示光头强能够获得最大的宝藏份数。

测试样例

3
6 2 3 3 2 3 2
4 3 2 2 3
6 1 3 1 1 3 1

8
6
6