Maximum Subarray Sum

You are given an array of integers. Your task is to find the maximum sum of any contiguous subarray. This sum can be written mathematically as \(\max_{1 \le i \le j \le n}\ sum_{k=i}^{j} a_k\), where \(a_k\) are the elements of the array.

You are expected to use Kadane's algorithm to solve this problem efficiently, with a time complexity of \(O(n)\) per test case.

The input begins with an integer \(T\) indicating the number of test cases. For each test case, the first line contains an integer \(N\) representing the number of elements, followed by a line containing \(N\) space-separated integers. For each test case, output the maximum subarray sum on a new line.

inputFormat

The input is read from stdin and is structured as follows:

T
N1
a1 a2 ... aN1
N2
b1 b2 ... bN2
...
NT
c1 c2 ... cNT

Where T is the number of test cases, and for each test case, the first number is the size of the array, followed by that many integers.

outputFormat

For each test case, output the maximum subarray sum on a separate line to stdout.

## sample

3
5
1 -2 3 4 -1
4
-5 -1 -8 -9
3
-2 -3 5

7
-1
5

</p>