Maximum Segment Sum

You are given T test cases. In each test case, you are provided with an integer N where N represents the number of elements in an array, followed by N integers. Your task is to compute the maximum sum of any contiguous segment (subarray) of the list.

The maximum segment sum can be mathematically defined as:

\(\max_{1 \leq i \leq j \leq N}\{a_i + a_{i+1} + \cdots + a_j\}\)

This is a classical problem that can be efficiently solved using Kadane's algorithm.

inputFormat

The first line of input contains a single integer T indicating the number of test cases. The following lines describe each test case.

• 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 representing the array elements.

outputFormat

For each test case, output a single line containing the maximum segment (subarray) sum.

## sample

1
5
1 2 3 -2 5

9

</p>