Anna is considering starting a paper route to make a little extra on the side. She has a number of streets she is looking to deliver to, each of which can be thought of as a sequence of houses. Each house pays as much as its occupants want for the paper, meaning that after factoring in the cost of the paper, some houses actually cost money to deliver to! Anna is under no obligation to deliver to any house, but is worried people would get upset if she delivered to their neighbours but not to them. Therefore she has decided to deliver to a contiguous run of houses on each street, even if some of those houses may reduce her total profit. Note that she may refuse to deliver to a street at all. Anna has already figured out the net profit as a result of delivering to each house, but would like your help figuring out the maximum profit she can make from delivering to each street. Can you write a program to help Anna?

Input Specification

The first line will contain an integer \(S\), the number of streets. Following this are \(2S\) lines, in pairs. The first line in each pair contains a single integer \(H\), the number of houses on this street. The second line contains \(H\) space-separated integers, \(p_i\), the profit from delivering a newspaper to the \(i\)th house.

Output Specification

Output \(S\) lines each containing a single integer: The maximum profit Anna can make on each street in the same order as they are given in the input.

Bounds

\(1 \leq S \leq 100\)

\(-1000 \leq p_i \leq 1000\)

Note this problem includes three sub-problems of increasing difficulty worth different numbers of points:

• 20 points: \(1 \leq H \leq 100\)
• 30 points: \(1 \leq H \leq 1000\)
• 50 points: \(1 \leq H \leq 10000\)

Sample Input

2
5
-1 3 -2 5 1
6
2 -3 2 4  -3 1

Sample Output

7
6

Sample Explanation

On the first street, the best route is to take all but the first house, \(3 + -2 + 5 + 1 = 7\). On the second street, the best route is to take just the two middle houses, \(2 + 4 = 6\).