Maximum Non-Overlapping Prefix and Suffix Sum

You are given an array of integers a of length n. You need to compute the maximum possible sum by considering prefix sums and suffix sums.

Let the prefix sum up to index i be defined as \(P[i] = \sum_{k=1}^{i} a_k\) and the suffix sum starting from index i be defined as \(S[i] = \sum_{k=i}^{n} a_k\). You are allowed to choose a prefix sum, or a suffix sum, or the sum of a prefix and a suffix provided that they do not overlap (i.e. if the prefix ends at index i, the suffix must start from index i+1).

Your task is to output the maximum achievable sum using one of these methods.

Note: If the array consists entirely of negative values, the answer will be the maximum (least negative) value among them.

inputFormat

The input is given from the standard input and has the following format:

T
n₁
a₁ a₂ ... aₙ₁
n₂
a₁ a₂ ... aₙ₂
...
nₜ
a₁ a₂ ... aₙₜ

Where T is the number of test cases. For each test case, the first line contains an integer n — the size of the array, followed by a line with n space‐separated integers.

outputFormat

For each test case, output a single integer — the maximum possible sum as described. Each result should be printed on a new line.

## sample

1
5
1 2 3 -2 5

9

</p>