Array Cancellation

You're given an array a of n integers, such that a_1 + a_2 + ⋅⋅⋅ + a_n = 0.

In one operation, you can choose two different indices i and j (1 ≤ i, j ≤ n), decrement a_i by one and increment a_j by one. If i < j this operation is free, otherwise it costs one coin.

How many coins do you have to spend in order to make all elements equal to 0?

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 5000). Description of the test cases follows.

The first line of each test case contains an integer n (1 ≤ n ≤ 10^5) — the number of elements.

The next line contains n integers a_1, …, a_n (-10^9 ≤ a_i ≤ 10^9). It is given that ∑_{i=1}^n a_i = 0.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

Output

For each test case, print the minimum number of coins we have to spend in order to make all elements equal to 0.

Example

Input

7 4 -3 5 -3 1 2 1 -1 4 -3 2 -3 4 4 -1 1 1 -1 7 -5 7 -6 -4 17 -13 4 6 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1 0

Output

3 0 4 1 8 3000000000 0

Note

Possible strategy for the first test case:

• Do (i=2, j=3) three times (free), a = [-3, 2, 0, 1].
• Do (i=2, j=1) two times (pay two coins), a = [-1, 0, 0, 1].
• Do (i=4, j=1) one time (pay one coin), a = [0, 0, 0, 0].

inputFormat

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 5000). Description of the test cases follows.

The first line of each test case contains an integer n (1 ≤ n ≤ 10^5) — the number of elements.

The next line contains n integers a_1, …, a_n (-10^9 ≤ a_i ≤ 10^9). It is given that ∑_{i=1}^n a_i = 0.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

outputFormat

Output

For each test case, print the minimum number of coins we have to spend in order to make all elements equal to 0.

Example

Input

7 4 -3 5 -3 1 2 1 -1 4 -3 2 -3 4 4 -1 1 1 -1 7 -5 7 -6 -4 17 -13 4 6 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1 0

Output

3 0 4 1 8 3000000000 0

Note

Possible strategy for the first test case:

• Do (i=2, j=3) three times (free), a = [-3, 2, 0, 1].
• Do (i=2, j=1) two times (pay two coins), a = [-1, 0, 0, 1].
• Do (i=4, j=1) one time (pay one coin), a = [0, 0, 0, 0].

样例

7
4
-3 5 -3 1
2
1 -1
4
-3 2 -3 4
4
-1 1 1 -1
7
-5 7 -6 -4 17 -13 4
6
-1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000
1
0

3
0
4
1
8
3000000000
0

</p>