Maximum Contiguous Acorns

You are given a series of test cases. For each test case, you are given an integer n and a list of n integers representing the number of acorns in each spot. Your task is to compute the maximum number of acorns that can be collected from any contiguous segment of spots.

This is a classic problem that can be solved using the Kadane's algorithm. The recurrence relation used in Kadane's algorithm is given by:

$$current\_max = \max(a_i, current\_max + a_i)$$

where a_i is the number of acorns at the i-th spot. The overall answer for a test case is the maximum value of current_max over the entire list of spots.

Input/Output: The input will be processed from the standard input (stdin) and the output should be produced to the standard output (stdout).

inputFormat

The first line of input contains an integer T representing the number of test cases.

For each test case, the first line contains an integer n representing the number of spots. The next line contains n space-separated integers, where each integer represents the number of acorns at that spot.

Example:

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

outputFormat

For each test case, output a single line containing the maximum sum of acorns that can be collected from any contiguous segment of spots.

Example:

6
-1

## sample

1
1
5

5

</p>