jean-and-the-evil

It's time for the Triwizard Tournament. Harry has been forced to compete
in the Tournament inspite of being under age. He has successfully 
completed the first two tasks of the tournament and is now placed 
jointly first with Cedric Diggory at 85 points. The third task
is to take place today. Professor Alastor Moody has put the cup at the centre
of the maze. The first one to reach the cup will win. Harry being a talented
and brave wizard reaches the centre of the maze. But still he has one
last hurdle to tackle before he can lift the cup and win. The hurdle is
as follows :

There are N chests placed in front of Harry. Each chest has a fixed number 
of potion bottles inside it. As we all know, some potions increase health 
and some decrease health. Harry has been weakened during his travel through
the maze. He does not have strength left to pick the cup. Now as there 
are health potions in front of him, he decides to regain some strength by 
drinking a few potions. But there is a rule that all must follow while
drinking potions. Harry may start from any chest and end at any chest.
But he must consume all the potions in all the chests between those two
starting and ending chests even if the potion weakens his health.
Harry does not know how much maximum health he can gain from the N chests
and he also does not have Hermonie by his side to help him out.
So he turns to you. Your task is to tell Harry the Maximum Health he 
can gain from the potions.

Note

There is partial marking for this question.

Input

First line contains T - the number of test cases.

Then T test cases follow.

The first line of each test case contains a single integer N - the
number of chests of potions.

The next line contains N integers representing the health that
Harry can gain or lose if he drinks potions from the chest.

Output

The maximum number of health that Harry can gain.

Constraints

1 ≤ T ≤50

1 ≤ N ≤ 10^6

-1000 ≤ Health ≤1000

Large Input data. Use scanf() and printf() instead of cout and cin

Problem Setter: Siddharth Seth

UPDATE

Harry has to consume atleast one potion.

SAMPLE INPUT
2
2
2 3
3
2 3 4

SAMPLE OUTPUT
5
9

Explanation

In both the test cases Harry can drink potions from all the chests to gain maximum health. All other combinations will result in lesser health.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: