Maximum Subarray Sum

You are given t test cases. For each test case, you are given an array of integers. Your task is to find the maximum sum of a contiguous subarray for each test case. This problem is a classic example of the Maximum Subarray Problem and can be solved efficiently using Kadane's Algorithm.

For an array \(a_1, a_2, \dots, a_n\), you need to compute the value:

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

Implement an algorithm that reads the input from stdin and writes the result to stdout.

inputFormat

The input is read from standard input (stdin).

The first line contains an integer t which denotes the number of test cases.

Each test case begins with an integer n representing the size of the array, followed by a line of n space-separated integers.

outputFormat

For each test case, output a single integer on a new line which is the maximum sum of any contiguous subarray for that test case. The output should be written to standard output (stdout).

## sample

2
3
1 2 3
4
2 1 3 4

6
10

</p>