Maximum Subarray Sum

You are given an array of integers and your task is to find the maximum possible sum of a contiguous subarray. This classic problem can be efficiently solved using Kadane's algorithm.

For an array \(a_1, a_2, \dots, a_n\), the recurrence relation of Kadane's algorithm can be formulated as:

\(dp_i = \max(a_i, dp_{i-1} + a_i)\)

The answer is \(\max\{dp_1, dp_2, \dots, dp_n\}\).

You need to handle multiple test cases. For each test case, first the integer n denotes the size of the array, followed by n space-separated integers.

inputFormat

The input begins with a single integer T (1 ≤ T ≤ 10), the number of test cases. Then for each test case:

1. An integer n (1 ≤ n ≤ 10⁵), the number of elements in the array.
2. A line containing n space-separated integers, where each integer is in the range of \(-10^9\) to \(10^9\).

The entire input is read from standard input.

outputFormat

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

The output should be printed to standard output.

## sample

1
5
1 -2 3 4 -5

7

</p>