#P2002. 我的,我的,都是我的!

我的,我的,都是我的!

念情发现了一些宝藏, 并且这些宝藏还是无穷无尽的!!念情正准备冲上去洗劫宝藏的时候,出来了一只护宝神兽

守护宝藏的神兽说:这里有N堆宝藏,他们都是无穷无尽的,你拿走之后,又会出现原来那么多的宝藏,不过你只能取连续的x堆宝藏,并且不能重复取连续的x堆宝藏。如果你这样做,所有的宝藏将消失。

念情很聪明,这点小问题不在话下,他完全能带走最多的宝藏,于是他大叫着:“我的!我的!都是我的!”,冲上去洗劫了一番。

现在告诉你每堆宝藏的宝藏数,你能知道念情这次得到了多少宝藏么?

 

Hint:

假设现在有三堆宝藏,每堆宝藏的宝藏数分别为 1  2  1

那么念情先取连续一堆: 1 + 2 + 1 = 4

再去连续两堆: ( 1 + 2 ) + ( 2 + 1 )= 6

最后取连续三堆:( 1 + 2 + 1 )= 4

所以念情拿走的宝藏为 14

Input

开始有一个整数T,表示T组测试数据
接下来每组开始一个N,表示有N堆宝藏
接下来一行有N个数,表示每堆宝藏的宝藏数
N<100,000
每堆宝藏的宝藏数<100,000

Output

输出念情带走的宝藏数

Sample Input

1
3
1 2 1

Sample Output

</p>
14

HINT

Source