Cậu bé ojboy là một game thủ nông trại kỳ cựu với hơn ~200~ giờ trong trò chơi Study Value. Trong trò chơi này, tưới cây là một phần quan trọng, song lại cần rất nhiều thời gian và công sức để thực hiện. Như vậy, để sau này việc tưới cây trở nên thuận tiện, ojboy quyết định rằng đã đến lúc thiết kế một hệ thống tưới tiêu tự động cho trang trại của mình.

Trang trại của ojboy có ~n~ trạm nước nằm trên một vòng tròn. Mỗi trạm thuộc một trong hai loại: nguồn nước hoặc khu trồng cây.

Mỗi nguồn nước ban đầu chứa một lượng nước nguyên dương. Mỗi khu trồng cây ban đầu chưa được tưới, nhưng cần nhận một lượng nước nguyên dương. Tổng lượng nước có sẵn ở tất cả các nguồn nước bằng đúng tổng lượng nước mà tất cả các khu trồng cây cần. Nhiệm vụ của bạn là chuyển toàn bộ nước từ các nguồn nước đến các khu trồng cây, sao cho mỗi khu trồng cây nhận đúng lượng nước cần thiết.

Do ojboy không biết cách kiếm tiền, cậu chỉ có thể mua được hai con robot vận chuyển nước giống nhau. Mỗi robot được đặt tại một trạm tùy ý. Robot sẽ xử lý trạm mà nó được đặt tại đó trước, rồi lần lượt di chuyển theo vòng tròn sang xử lí các trạm tiếp theo. Robot dừng lại sau khi đã xử lý đủ cả ~n~ trạm, mỗi trạm đúng một lần.

Cụ thể hơn, nếu một robot bắt đầu tại trạm ~s~, thì thứ tự các trạm mà robot xử lý là: ~s, s+1, s+2, \ldots, n, 1, 2, \ldots, s-1~.

Ban đầu mỗi con robot không chứa nước, và có sức chứa không giới hạn.

Khi một robot xử lý một trạm:

• nếu đó là một nguồn nước, robot có thể lấy một lượng nước nguyên không âm bất kỳ từ trạm đó, miễn là không vượt quá lượng nước còn lại tại nguồn;

• nếu đó là một khu trồng cây, robot có thể đổ một lượng nước nguyên không âm bất kỳ vào trạm đó, miễn là không vượt quá lượng nước mà khu trồng cây đó còn thiếu.

Robot không được thực hiện bất kỳ thao tác nào khác với một trạm. Cụ thể, robot không thể đổ nước vào nguồn nước, không thể lấy nước từ khu trồng cây, và không thể để nước lại tại một trạm để robot còn lại lấy sau.

Bạn được chọn hai trạm xuất phát của hai con robot và lập trình toàn bộ hành động của chúng.

Hãy giúp ojboy đếm số cách chọn hai trạm xuất phát sao cho hệ thống có thể hoàn thành nhiệm vụ. Sau khi cả hai con robot kết thúc hành trình, toàn bộ nước ở các nguồn nước phải được chuyển đến các khu trồng cây, và mọi khu trồng cây phải được tưới đủ lượng nước cần thiết.

Hai cách chọn được cho là khác nhau khi có một trạm xuất được chọn ở cách này nhưng không được chọn ở cách kia. Nói cách khác, chọn hai trạm ~(x, y)~ cũng giống như chọn ~(y, x)~. Được phép chọn ~(x, x)~.

Input

Dòng đầu tiên chứa số nguyên ~t~ (~1 \le t \le 10^4~) — số lượng test case. Mô tả của mỗi test case như sau.

• Dòng đầu tiên chứa số nguyên ~n~ (~2 \le n \le 2 \cdot 10^5~) — số lượng trạm.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~-10^9 \le a_i \le 10^9~, ~a_i \ne 0~).

  Nếu ~a_i > 0~, trạm ~i~ là một nguồn nước chứa ~a_i~ đơn vị nước. Nếu ~a_i < 0~, trạm ~i~ là một khu trồng cây cần ~-a_i~ đơn vị nước.

Dữ liệu đảm bảo rằng ~a_1 + a_2 + \ldots + a_n = 0~ với mỗi test case.

Tổng ~n~ trên tất cả test case không vượt quá ~2 \cdot 10^5~.

Output

Với mỗi test case, in ra một số nguyên — số cặp trạm xuất phát hợp lệ.

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

Trong test case đầu tiên, có hai trạm: trạm ~1~ là nguồn nước chứa ~1~ đơn vị nước, còn trạm ~2~ là khu trồng cây cần ~1~ đơn vị nước.

Các cách chọn hai trạm xuất phát hợp lệ là: ~(1,1),\ (1,2)~.

Trong cả hai cách trên, có thể lập trình robot lấy nước từ trạm ~1~ rồi đổ vào trạm ~2~. Vì vậy, đáp án là ~2~.

—

Trong test case thứ hai, dãy đã cho là: ~[ -2,\ 1,\ 1 ]~.

Trạm ~1~ cần ~2~ đơn vị nước, còn hai trạm ~2~ và ~3~ mỗi trạm chứa ~1~ đơn vị nước.

Các cách chọn hai trạm xuất phát hợp lệ là: ~(1,2),\ (2,2),\ (2,3)~.

Với mỗi cách chọn trên, hai robot có thể thu đủ nước trước khi cần tưới cho trạm ~1~. Vì vậy, đáp án là ~3~.

—

Trong test case thứ ba, dãy đã cho là: ~[5,\ -3,\ 6,\ -7,\ -1]~.

Các cách chọn hai trạm xuất phát hợp lệ là: ~(1, 1),\ (1, 2),\ (1, 3),\ (1, 4),\ (1, 5),\ (2, 5),\ (3, 5)~.

Do đó, đáp án là ~7~.