Description

给定一个长度为N的int型数组a[0,1,2,...N-1], 请计算最大子数组和.

Input

第一行输入M表示包含M组测试数据，每组先输入N (N<=50000), 接着输入N个int型整数.

Output

输出最大子数组和.

Sample Input

2
5 -1 -5 -2 -1 -3
5 2 -1 3 -2 4

Sample Output

-1
6