Maximum Subarray Sum with One Change

You are given an array \( A \) of \( N \) integers. Your task is to find the maximum sum of any non-empty contiguous subarray of \( A \) after performing at most one change. A change consists of assigning an arbitrary value (in this problem, it is always optimal to change an element to \( 0 \)) to any one element of the array.

For example, consider the array [1, -2, 3, 4, -5]. Without any change, the maximum subarray sum is \( 3+4=7 \). However, by changing \( -2 \) to \( 0 \), the array becomes [1, 0, 3, 4, -5] and the maximum subarray sum becomes \( 1+0+3+4=8 \).

If the array contains only negative numbers, you might obtain a non-negative sum by performing a change. For instance, for the array [-1, -2, -3], by changing any element to \( 0 \), the maximum subarray sum becomes \( 0 \).

Your program should be able to handle multiple test cases. For each test case, read the input from standard input and output the answer to standard output.

inputFormat

The first line of input contains an integer \( T \) denoting the number of test cases. For each test case, the first line contains an integer \( N \) (the number of elements in the array). The next line contains \( N \) space-separated integers representing the array \( A \).

Example:

4
5
1 -2 3 4 -5
3
-1 -2 -3
7
2 -1 2 3 -9 4 5
1
-5

outputFormat

For each test case, output a single line containing the maximum subarray sum after performing at most one change.

Example:

8
0
15
0

## sample

4
5
1 -2 3 4 -5
3
-1 -2 -3
7
2 -1 2 3 -9 4 5
1
-5

8
0
15
0

</p>