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.
#!/usr/bin/python

def R(): return map(int, raw_input().split())

T = R()[0]
for i in range(T):
    N = R()[0]
    A = R()
    all_negative = True
    max_element = None
    max_so_far = 0
    max_ending_left = 0     # maximum subsequence ending at prev position
    max_skipped_one = 0     # maximum subsequence ending at curr position where one element was skipped
    for x in A:
        max_element = max(max_element, x)
        all_negative = all_negative and x < 0

        max_ending_left, max_skipped_one  = max(0, max_ending_left + x), max(0, max_ending_left, max_skipped_one + x)
        max_so_far = max(max_so_far, max_skipped_one)

    print max_element if all_negative else max_so_far