Description

给你一串数字,求一个最大的连续部分,使得这部分和最大,取的部分长度至少为1

Input

首先一个t表示有t组数据.然后是t组数据.
每组首先包含一个n,表示有n个数字,然后是这n个数字(n<=1000000),数字不超过1000000

Output

一个数字,最大的部分和

Sample Input

1
5
-1 1 9 -2 3

Sample Output

11

HINT

Source

CX