Maximum Point Gain

In this problem, you are given several test cases. Each test case contains a number of rounds and a sequence of point changes. Your task is to compute the maximum point gain over any contiguous subsequence of rounds. This is a classic problem that can be efficiently solved using Kadane's algorithm.

The algorithm works as follows: iterate over the rounds and, at each step, maintain the maximum sum ending at the current round. The answer for a test case is the maximum of all these sums. The optimal solution should work in O(n) time per test case.

Input: The input starts with an integer T, the number of test cases. For each test case, the first line contains an integer N denoting the number of rounds, and the second line contains N space-separated integers representing the point changes.

Output: For each test case, output the maximum contiguous point gain on a new line.

The underlying formula for the maximum subarray sum can be described in LaTeX as follows:

\[ \max_{1 \leq i \leq j \leq N} \sum_{k=i}^{j} a_k \]

inputFormat

The first line of input contains a single integer T, the number of test cases. Each test case consists of two lines. The first line contains an integer N, the number of rounds. The second line contains N space-separated integers which represent the point changes in each round.

Example:

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

outputFormat

Output T lines, each line containing a single integer which is the maximum point gain for the corresponding test case.

Example:

4
10

## sample

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

4
10

</p>