Maximum Discount Coupon Value

You are given several datasets representing daily meal expenses. In each dataset the expenses (which can be positive or negative) are listed for consecutive days. Your task is to compute the maximum discount coupon value for each dataset. This is equivalent to finding the maximum sum of any contiguous subarray.

Mathematically, for a given array \(S = [s_1, s_2, \dots, s_n]\), you need to compute:

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

If all the numbers are negative, then the answer is the maximum (least negative) number in the array.

inputFormat

The input is read from stdin and is structured as follows:

1. The first line contains an integer \(T\), the number of test cases.
2. For each test case, the first line contains an integer \(N\), the number of days.
3. The next line contains \(N\) space-separated integers representing the daily meal expenses.

outputFormat

For each test case, output a single line with the maximum discount coupon value (i.e. the maximum contiguous subarray sum) computed for that dataset. The output should be written to stdout.

## sample

1
5
3 -2 5 -1 2

7

</p>