Maximum Contiguous Subarray Sum

You are given several test cases. In each test case, you are given a sequence of integers which represent the production rates of a sequence of stations. Your task is to find the maximum possible sum of any contiguous subarray for each test case.

In mathematical terms, for an array \(a_1, a_2, \ldots, a_n\), find the maximum value of \(\sum_{i=l}^{r} a_i\) for any \(1 \leq l \leq r \leq n\). This is a classic problem that can be solved using Kadane's algorithm.

inputFormat

The first line of input contains a single integer \(T\) (\(T \ge 1\)) representing the number of test cases.

For each test case:

• The first line contains an integer \(N\) (\(1 \leq N \leq 10^5\)), the number of stations.
• The second line contains \(N\) space-separated integers representing the production rates (which can be negative, zero, or positive).

outputFormat

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

## sample

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

10
-1

</p>