Maximum Subsequence Sum

Given an integer sequence \(a_1, a_2, \ldots, a_n\), find the maximum sum of any contiguous subsequence of the array. Formally, you need to compute

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

If all numbers are negative, the answer is the maximum (i.e. the least negative) number in the sequence.

You will be given multiple test cases. For each test case, output the maximum contiguous subsequence sum on a separate line.

inputFormat

The input begins with an integer \(T\) (the number of test cases). Each test case is described with two lines:

1. The first line contains an integer \(n\) representing the number of elements in the sequence.
2. The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\).

outputFormat

For each test case, print one integer: the maximum sum of a contiguous subsequence from the given sequence. Each answer should be printed on its own line.

## sample

1
5
1 -2 3 4 -5

7

</p>