SABBIRGAME - Sabbir and Game

Sabbir is a little boy. he loves to play. One day his friend Taskin suggested a new interesting game. There are n levels in the game. One should pass all the levels with a positive life-point. In some level one can increase his life-point by defeating the villain of the game or lose some life-point when one can't defeat the villain. Sabbir knows the points he is going to lose or increase in each level. Determine the minimum life-point Sabbir should have initially (at the starting of the game) to pass all the levels with a positive life point.

Input

Input consists of at most 100 test cases.

First line consists of a single integer T (1 <= T <= 100) number of test cases.

Each test case is consists of two lines. first line consists of an integer n (1 <= n <= 1000)

Second line consists of n space separated integer a1, a2 ... an-1, an (-107 <= ai <= 107)

Output

for each test case print an integer in one line , the minimum life-point Sabbir will need initially.

Example

Input:
3
3
5 -8 3
4
1 2 -3 5
3
1 0 3

Output:
4
1
0

Explanation

First case, if Sabbir have 4 life-points at first. Sabbir will have 9 points after playing 1st level, he will have 1 point after playing 2nd level, he will have 4 points after playing 3rd level... his points never becomes less than 1 (remains positive). If he starts with a lower point (less than 4) initially, he will die at the 2nd level and can't pass all the levels. So, 4 is the minimum answer.


Added by:sabbir
Date:2017-02-21
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2019-04-28 21:24:37
Nice Problem @sabbir vai
2019-01-08 19:23:52
ohh,finally got ac...
2018-11-05 17:58:35
my 50th
but it takes 40 days
2018-01-04 10:10:01
used a good concept of ternary operator.... :)
2017-06-21 18:40:09
pls check for submission id 19654968. could u tell me where is the bug? thx before
2017-04-30 09:27:52
@sachinverma there is a mistake in your code. I can't tell that in comments. try to find out.
2017-04-27 20:11:10 Sachin verma
@sabbir will you please check my submission. I cannot understand my mistake. Thank you.
2017-03-18 22:07:28 Marcin
What should be the answer for the following test case:
1
1
0

Should it be 0 or 1?

Edit: got it, it's 1

Last edit: 2017-03-18 22:15:57
2017-03-14 11:44:17 Somdip Sen
sd_singh: what is it you need ?
2017-03-07 07:28:05 Karsten Ari Agathon
I think it will be better if stated that the minimum life-point initially must larger or equal to 0.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.