Maximum Subarray Sum

You are given T test cases. For each test case, you are provided with an array of integers. Your task is to compute the maximum sum of a contiguous subarray for each test case.

The maximum subarray sum is defined as the largest sum of consecutive elements of the array. One efficient approach to solve this problem uses Kadane's algorithm, which iteratively computes the following recurrence: $$ max\_current = \max(a_i, max\_current + a_i) $$ where \(a_i\) is the i-th element of the array. Your solution should process input from stdin and output the answer for each test case to stdout, one per line.

inputFormat

The first line of the input contains an integer T denoting the number of test cases. Each test case consists of two parts:

• The first integer N indicates the number of elements in the array.
• Followed by N space-separated integers representing the array elements.

All input is given via stdin.

outputFormat

For each test case, output a single line containing the maximum subarray sum. All output should be printed to stdout.

## sample

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

6
-1
11

</p>