Maximum Prefix Sum

You are given T test cases. For each test case, you are given an integer N followed by a sequence of N integers. Define the prefix sum for the sequence as:

$$S_i = \sum_{j=1}^{i} a_j$$

Your task is to compute the maximum prefix sum for each test case. In other words, for each test case, you must determine the maximum value among \(S_1, S_2, \dots, S_N\). Note that if all partial sums are negative, the maximum prefix sum is the largest among them.

Input will be provided via stdin and you should output the result for each test case on a new line to stdout.

inputFormat

The first line contains a single integer T denoting the number of test cases. For each test case, the first line contains an integer N — the length of the sequence. The second line contains N space-separated integers representing the sequence.

outputFormat

For each test case, output a single integer representing the maximum prefix sum of the sequence. Each result should be printed on its own line.

## sample

1
5
1 -2 3 4 -1

6

</p>