You are given an array \(A\) consisting of \(N\) elements. Your task is to find the maximal subarray sum after applying the following operation exactly once:

Select any subarray and set all the elements in it to zero.

Input format

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

Output format

Print \(T\) lines. For each test case, print a single line representing the maximal subarray sum after applying the operation no more than once.

Constraints

\(1 \leq T \leq 20000\)

\(1 \leq N \leq 500000\)

\(0 \leq |A_i| \leq 10^9 \forall i \in[1,N]\)

Sum of \(N\) over all test cases does not exceed \(10^6\)