You're given an array of N integer numbers.
The maximal sum of the array is the maximal sum of the elements of a nonempty consecutive subarray of this array. For example, the maximal sum of the array [1, -2, 3, -2, 5] is 6 because the sum of the subarray [3, -2, 5] is 6 and it is impossible to achieve greater subarray sum.
Now you're allowed to remove no more than one element from the given array. What is the maximal possible maximal sum of the resulting array you can achieve by doing so?

Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of elements in the given array.
The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array.

Output
For each test case, output a single line containing the maximal possible maximal sum of the array obtained by removing no more than one integer from the initial array.

Constraints

1 ≤ T ≤ 10
2 ≤ N ≤ 10^5
-10^9 ≤ Ai ≤ 10^9

Example
Input:
2
5
1 -2 3 -2 5
2
-1 -2

Output:
8
-1

Explanation
Example case 1. As shown in the statement, the maximal sum of the initial array is 6, but if you remove the fourth element (i.e. -2), then the array [1, -2, 3, 5] will have subarray [3, 5] and the value of the maximal sum will be equal to 8.

见题面

见题面