Maximum Subarray Sum

You are given T test cases. For each test case, you are given an array of integers. Your task is to compute the maximum subarray sum. In other words, you must find the maximum value of the sum of a contiguous subarray.

This can be formally defined as follows:

$$\max_{1 \leq i \leq j \leq n} \left(\sum_{k=i}^{j} a_k\right)$$

Use an efficient algorithm (such as Kadane's algorithm) to solve the problem.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains an integer T (1 ≤ T ≤ 10), the number of test cases.
2. For each test case, the first line contains an integer n (1 ≤ n ≤ 10⁵), the number of elements in the array.
3. The next line contains n space-separated integers representing the elements of the array.

It is guaranteed that the absolute value of each integer does not exceed 10⁴.

outputFormat

For each test case, print the maximum subarray sum on a new line to stdout.

## sample

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

5
4
6

</p>