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\)