Ojboy is a famous professional gamer who had more than ~200~ hours of playing experience with a cozy farming game called Study Value. In this game, crop watering is an essential part of the game, but consumes a lot of time and energy. Therefore, for later convenience, he decides to spend a whole day building an automated watering system, as follows:

There are ~n~ water stations arranged in a circle. Each station is either a source or a sink.

A source initially contains a positive integer amount of water. A sink initially contains no water, but requires a positive integer amount of water. The total amount of water in all sources is equal to the total demand of all sinks. The task is to transfer all water from the sources to the sinks, so that every sink receives exactly its required amount.

Since ojboy doesn't know how to make money, he can only afford two indistinguishable assistant robots to help with the task. Each robot starts at one chosen station and first interacts with that station. Then, it repeatedly moves to the next station in a circle until it has interacted with each of the ~n~ stations exactly once.

Formally, a robot starting at station ~s~ visits the stations in the order: ~s, s+1, s+2, \ldots, n, 1, 2, \ldots, s-1~.

Each robot starts without carrying any water and has unlimited carrying capacity.

When a robot visits a station:

• if it is a source, the robot may take any non-negative integer amount of water from it, without exceeding its remaining supply;

• if it is a sink, the robot may pour any non-negative integer amount of water into it, without exceeding its remaining demand.

Robots cannot perform any other kind of interaction with a station. In particular, they cannot pour water into a source, take water from a sink, or leave water at a station for the other robot to pick up later.

You may choose the two starting stations and program the actions of both robots.

Help ojboy clear the quest by finding how many valid deployments of the two robots are possible. After both robots finish, all source water must have been moved into sinks, and all sink demands must be fully satisfied.

Two choices are considered different if and only if a start station is chosen in a choice but not chosen in the other. In other words, choosing stations ~(x, y)~ is the same as choosing ~(y, x)~. Choosing ~(x, x)~ is allowed.

Input

The first line contains an integer ~t~ (~1 \le t \le 10^4~) — the number of test cases. The description of each test case is as follows.

• The first line of each test case contains an integer ~n~ (~2 \le n \le 2 \cdot 10^5~) — the number of stations.

• The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~-10^9 \le a_i \le 10^9~, ~a_i \ne 0~).

  If ~a_i > 0~, station ~i~ is a source containing ~a_i~ units of water. If ~a_i < 0~, station ~i~ is a sink requiring ~-a_i~ units of water.

It is guaranteed that ~a_1 + a_2 + \ldots + a_n = 0~ for each test case.

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

Output

For each test case, output one integer – the number of valid ways to choose the two starting stations.

Scoring

Sample Input 1

5
2
1 -1
3
-2 1 1
5
5 -3 6 -7 -1
8
3 -5 2 -4 6 -1 -3 2
13
4 -2 -3 7 -6 1 -5 8 -4 2 -1 -3 2

Sample Output 1

2
3
7
16
54

Notes

In the first test case, there are two stations: station ~1~ is a source with ~1~ unit of water, and station ~2~ is a sink requiring ~1~ unit of water.

The valid unordered choices of starting stations are: ~(1,1),\ (1,2)~.

For both choices, at least one robot can visit station ~1~ before station ~2~, take the water from the source, and pour it into the sink. Therefore, the answer is ~2~.

—

In the second test case, the array is: ~[ -2,\ 1,\ 1 ]~.

Station ~1~ needs ~2~ units of water, while stations ~2~ and ~3~ each contain ~1~ unit.

The valid unordered choices are: ~(1,2),\ (2,2),\ (2,3)~.

In each of these choices, the robots can collect enough water before reaching station ~1~. Therefore, the answer is ~3~.

—

In the third test case, the array is: ~[5,\ -3,\ 6,\ -7,\ -1]~.

The valid unordered choices of starting stations are: ~(1, 1),\ (1, 2),\ (1, 3),\ (1, 4),\ (1, 5),\ (2, 5),\ (3, 5)~.

Hence, the answer is ~7~.