Problem Description

给定一个序列 $a[1],a[2],a[3]......a[n]$，你的任务是计算其连续子段的最大和。例如，给定 $(6,-1,5,4,-7)$，该序列中的最大和为 $6+(-1)+5+4=14$。

Input

第一行输入包含一个整数 $T(1≤T≤1000)$ 表示后续测试数据的组数。接下来 $T$ 行每行由一个整数 $N(1≤N≤100000)$ 开始，接下来 $N$ 个整数 $A_i(-1000≤A_i≤1000)$。

每个测试点的 $\sum N≤2×10^5$。

Output

对每组测试数据，输出最大的子段和。

Sample

2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

14
7