Score

Input

The first line contains one integer $t$ (1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains one integer $n$ (1 \le n \le 5 \cdot 10^5) — the length of the array.

The second line of each test case contains $n$ integers a_1, a_2, \dots, a_n (-10^9 \le a_i \le 10^9) — the elements of the array.

It is guaranteed that the sum of $n$ does not exceed 5 \cdot 10^5.

Output

For each test case, output the total $\text{score}$ of the array.

Examples

Note

For the first test case:

For example, if a=[1,2,3], the $\text{score}$ will be computed as follows:

• [\mathbf{1},2,3] \rightarrow 1 < 5 \xrightarrow{-1} -1

• [1,\mathbf{2},3] \rightarrow 2 < 4 \xrightarrow{-1} -2

• [1,2,\mathbf{3}] \rightarrow 3 = 3 \xrightarrow{3} 1

• [\mathbf{1,2},3] \rightarrow 3 = 3 \xrightarrow{3} 4

• [1,\mathbf{2,3}] \rightarrow 5 > 1 \xrightarrow{2} 6

• [\mathbf{1,2,3}] \rightarrow 6 > 0 \xrightarrow{2} 8

Thus, the total $\text{score}$ of the array equals -1 - 1 + 3 + 3 + 2 + 2 = 8, note that the sum of the remaining numbers is 0 when considering the entire array as a segment.

The second test case has three subsegments: $[1]$, $[-1]$, $[1,-1]$, which correspond to wonderful, normal, and perfect, with a score of 2+3-1=4.

Scoring

1. ($5$ points) : a_i=1 (1 \le i \le n)

2. ($10$ points) : (1 \le \sum n \le 100)

3. ($20$ points) : (1 \le \sum n \le 2000)

4. ($25$ points) : (1 \le \sum n \le 2 \cdot 10^5)

5. ($50$ points) : (0 \le a_i \le 10^9)

6. ($50$ points) : (0 \le \sum_{i=1}^n |a_i| \le 10^9)

7. ($75$ points) : no additional constraints