Optimal Fruit Collection

You are given a row of trees, where each tree has a non-negative number of fruits. For each test case, you are provided with an integer N indicating the number of trees and a list of N integers representing the fruits on each tree. You need to choose a tree as a pivot and then decide on one of the two strategies:

• Collect all fruits from the beginning of the row up to (and including) the pivot tree.
• Collect all fruits from the pivot tree to the end of the row.

Your task is to determine the maximum number of fruits that can be collected by making an optimal choice of the pivot tree and the direction. Mathematically, for an array \(A = [a_1, a_2, \dots, a_N]\), you need to compute: \[ \max \Bigg\{\max_{1 \le i \le N} \left(\sum_{j=1}^{i} a_j\right), \; \max_{1 \le i \le N} \left(\sum_{j=i}^{N} a_j\right)\Bigg\} \] for each test case.

inputFormat

The input is given via standard input (stdin) 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, an integer N is given on a new line followed by a line containing N space-separated non-negative integers, which denote the number of fruits on each tree.

outputFormat

For each test case, output a single integer on a new line representing the maximum number of fruits that can be collected using the optimal strategy.

## sample

6
4
1 5 3 2
5
2 4 1 0 3
1
7
3
0 0 0
4
1000 1000 1000 1000
7
0 0 7 0 0 0 0

11
10
7
0
4000
7

</p>