Time Limit:1000ms Memory Limit:65536KB

Description

给一个整数数组A={a1,a2,…an},
将这个数组首尾相接连成一个环状,它的一个子序列是指这个数组连续的一段,
比如a2,a3…ak,或者an,a1…ai。请从这个环上选取两个不重叠的非空子序列,使这两个子序列中的所有数字之和最大。
在三个样例中分别选取的子序列是:
样例一: {a1} {a3}
样例二: {a1} {a3}
样例三: {a5,a1} {a3}

Input

输入的第一行包含一个正整数T(1<=T<=40),表示有T组测试数据。
接下来每个测试数据包含两行,
第一行是一个正整数n(2<=n<=50000), 
第二行是用空格隔开的数组A的n个数,依次为a1,a2,…an (|ai|<=10000)。 

Output

每组数据输出一行,包含一个数,即所求的这两个子序列的元素之和。

Sample Input

3
3
1 -1 0
4
1 -1 1 -1
5
1 -1 1 -1 1


Sample Output

1
2
3

Hint


Author

Source

2010年有道难题资格赛(1)