Maximum Beauty Subsegment

You are given several test cases. For each test case, you are provided with a row of flowers represented as an array of integers where each integer denotes the beauty value of a flower. Your task is to find the maximum sum of any continuous subsegment in the row. This problem is a classic example where the Kadane's algorithm is applied.

More formally, given an array \(a_1, a_2, \ldots, a_n\), you need to compute the maximum value of:

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

You need to output the maximum subsegment sum for each test case in a new line.

Note: The input is provided via stdin and the output should be printed to stdout.

inputFormat

The input consists of multiple test cases. The first line contains an integer \(T\) denoting the number of test cases. For each test case:

• The first line contains an integer \(n\) indicating the number of flowers (elements in the array).
• The second line contains \(n\) space-separated integers, representing the beauty values.

All input is given through stdin.

outputFormat

For each test case, output the maximum sum of any continuous subsegment on a new line. The output should be sent to stdout.

## sample

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

7
-1

</p>