DevuLand is a very strange place. There are n villages in it. Some of the villages are occupied by dinosaurs while the remaining ones by villagers.
	You are given the information of DevuLand 
	by an array D of size n. If D[i] is non-negative, it means that there are D[i] villagers in that village. 
	Otherwise, it means that are -D[i] 
	dinosaurs in that village.

	It is also guaranteed that total number of villagers in DevuLand is equal to total number of dinosaurs.

Once dinosaurs got very hungry and started eating villagers. Frightened villagers gathered immediately and met their Sarpanch Deviji. Deviji, being a very daring and negotiable person, met to the head
of dinosaurs. Soon both parties called a truce. It was decided that the villagers will provide laddus to 
the dinosaurs. So everyday, each villager will take exactly one laddu to one of the dinosaurs in such a way that no dinosaur remains hungry (note that this is possible because number of villagers is the same as the number of dinosaurs).

Actually, carrying laddus is a quite a tough job. Villagers have to use a bullock cart for that. It takes one unit of grass a bullock to 
carry a cart with 1 laddu for 1 kilometre. Laddus used to be very heavy in DevuLand, so a bullock cart can not carry more than one laddu.

It is also given distance between village indexed i and j is |j - i| (the absolute value) kilometres.

Now villagers sat down and found a strategy to feed laddus to dinosaurs so that they need to buy the least amount of grass from the nearby market. 
They are not very good in 
calculations, please find out what is the minimum number of units of grass they need to buy.

-----Input-----

First line of the input contains an integer T denoting number of test cases.

For each test case, there are two lines. 

First line contains a single integer denoting n: number of villages. 

Second line contains n space separated integers denoting the array D.

-----Output-----

For each test case, print a single line containing the integer corresponding to answer of the problem.

-----Constraints-----

-  1 ≤ T ≤ 10^5 
-  1 ≤ n ≤ 10^5 
-  -10^4 ≤ D[i] ≤ 10^4 
-  Sum of n over all the test cases will be ≤ 10^6 
-  It is guaranteed that sum of D[i] is zero for a single test case which ensures that there are equal number of villagers and dinosaurs. 

-----Example-----
Input:
3
2
5 -5
2
-5 5
3
1 2 -3
Output:
5
5
4

-----Explanation-----
Example case 1. Each villager in village 1, need to walk 1 km to reach to the dinosaur in 2nd village.
Example case 2. Each villager in village 2, need to walk 1 km to reach to the dinosaur 1st village.
Example case 3. Each villager in village 1, need to walk 2 km to reach to the dinosaur in 3rd village whereas Each villager in village 2, 
need to walk 1 km to reach to the dinosaur in 3rd village.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\nfor _ in range(int(input())):\n n = int(input())\n a = list(map(int, input().split()))\n curr = 0\n ans = 0\n for x in a:\n  curr += x\n  ans += abs(curr)\n print(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13011