Maximum Subarray Sum

You are given an array of integers. Your task is to find the maximum sum of any contiguous subarray. More formally, given an array \(a = [a_1, a_2, \dots, a_n]\), find the value of

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

Note that the subarray must contain at least one element.

You will be provided with multiple test cases. For each test case, the first line contains an integer \(n\) representing the number of elements in the array, followed by a line with \(n\) space-separated integers. The first input line will contain \(T\), the number of test cases.

Your task is to compute and output the maximum contiguous subarray sum for each test case. Use an efficient algorithm such as Kadane's algorithm to solve this problem.

inputFormat

The first line of input contains a single integer \(T\), the number of test cases. For each test case:

• The first line contains an integer \(n\) (the number of elements in the array).
• The second line contains \(n\) space-separated integers.

All input should be read from stdin.

outputFormat

For each test case, output the maximum subarray sum on a new line. All output should be written to stdout.

## sample

2
5
1 -2 3 4 -1
8
-2 -3 4 -1 -2 1 5 -3

7
7

</p>