Maximum Contiguous Flowers Sum

You are given several test cases. In each test case, a sequence of integers is provided, where each integer represents the number of flowers in a flower bed. Your task is to determine the maximum sum of flowers that can be obtained by selecting a contiguous subarray (i.e. a sequence of consecutive flower beds) from the given sequence.

More formally, given a sequence \(a_1, a_2, \dots, a_n\), you need to compute:

[ \max_{1 \le i \le j \le n} \sum_{k=i}^{j} a_k ]

Note that the sequence may include negative numbers which denote a reduction in the number of flowers. If all numbers are negative, the answer is the largest (i.e. the least negative) number among them.

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer \(T\), the number of test cases.
• For each test case, the first line contains an integer \(N\), the number of flower beds.
• The second line contains \(N\) space-separated integers representing the number of flowers in each bed.

Note that multiple test cases are provided in one input.

outputFormat

For each test case output a single line containing the maximum contiguous sum of flowers for that test case.

## sample

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

10
-1

</p>