C. Smartass (Hard Version) - Grey
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

roshi and mhna were debating whether there are more طلعات or نزلات in Jordan. And guess what. You're damn right. Aboud and Fakher are still playing 2v2v2v2. Anyways for absolutely no reason. Literally no reason. mhna decided to give roshi a problem and said he's "stoopid" if he can't solve it. Can you help roshi prove he isn't stoopid?

This is the hard version of the problem. The only difference between the easy and hard version is the constraint on $$$n$$$

You are given an array $$$a$$$ of length $$$n$$$ consisting of integers

A subarray $$$a_l,a_{l+1},…,a_r$$$ is good if it isn't empty and the sum of elements of this subarray is zero $$$(\sum_{i=l}^{r} a_i = 0)$$$

Calculate the number of good subarrays in the array $$$a$$$

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1≤t≤10^5)$$$ — the number of test cases

The first line of each test case contains an integer $$$n$$$ $$$(1≤n≤10^5)$$$ — the length of the array

The second line of each test case consists of $$$n$$$ integers $$$a_1,a_2,…,a_n$$$ $$$(-10^9≤a_i≤10^9)$$$ — the elements of the array $$$a$$$

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

Output

Print $$$t$$$ lines, each line containing the answer to the corresponding test case — the number of good subarrays in the array $$$a$$$

Example
Input
4
1
0
3
1 -1 0
5
1 2 3 4 5
10
1 2 3 -3 0 -2 -1 0 0 3
Output
1
3
0
13