Maximum Subarray Sum

Given an array of integers, your task is to find the maximum sum of any non-empty contiguous subarray using Kadane's algorithm.

In other words, for an array (a_1, a_2, \ldots, a_n), find
[\max_{1 \leq i \leq j \leq n} \left(\sum_{k=i}^{j} a_k\right)].

You need to support multiple test cases. All input will be read from stdin and all output should be written to stdout.

inputFormat

The first line contains an integer (T) (at least 3) denoting the number of test cases. Each test case starts with an integer (N) indicating the number of elements in the array, followed by (N) space-separated integers.

outputFormat

For each test case, output a single line containing the maximum subarray sum.## sample

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

4
-1
6