Maximum Subarray Sum

You are given an array of integers and your task is to find the maximum sum of a contiguous subarray. If the array consists entirely of negative numbers, then the answer is the maximum (least negative) element.

This problem can be solved using the well-known Kadane's Algorithm. The algorithm computes the maximum subarray sum by iterating through the array and using the recurrence relation:

$$current\_max = \max(a_i,\, current\_max + a_i)$$

and updating the global maximum:

$$max\_so\_far = \max(max\_so\_far,\, current\_max)$$

Your program should read multiple test cases from standard input and output the result for each test case on a new line.

inputFormat

The input is given from standard input and has the following format:

1. The first line contains an integer T representing the number of test cases.
2. For each test case, the first line contains an integer n representing the number of elements in the array.
3. The second line contains n space-separated integers, which are the elements of the array.

outputFormat

For each test case, output one line containing the maximum sum of a contiguous subarray.

## sample

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

7
-1

</p>