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.