Description

给定一个长度为 $n$ 的整数序列 $S$ ,使得 $s_1+s_2+\cdots+s_n=0$。

你可以做一种操作，选择不同的 $i$ 和 $j(1\leq i,j\leq n)$,可以使得 $a_i = a_i - 1$ 、$a_j=a_j+1$。如果操作中 $i < j$,则操作免费，反之，操作会需要消耗一个能量值。

至少需要消耗多少能量值才能使得整个序列都变成 $0$ 呢

Input Format

包含多组样例，第一行描述了组数 $T$，接下来有 $T$ 组数据（$T\in [1, 5000]$）：

第一行数据包括一个整数 $n$ 代表元素数量（$n \in [1, 10^5]$）;

第二行有 $n$ 个整数 $s_1,s_2,\cdots,s_n(s_i \in [-10^9 , 10^9])$，保证$\sum_{i=1}^{n}s_i=0$;

Output Format

对于每一组样例输出最少我们需要多少能量值才可以使得所有的元素都归零。

4
4
-3 5 -3 1
2
1 -1
4
-3 2 -3 4
4
-1 1 1 -1​

3
0
4
1​

Hint

第一组样例：

$i=2,j=3$ ==>[-3,2,0,1]花费0

$i=2,j=1$ ==>[-1,0,0,1]花费2

$i=2,j=3$ ==>[0,0,0,0]花费1