[Solution] Zero-Sum Prefixes Codeforces Solution

C. Zero-Sum Prefixes

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The score of an array 𝑣1,𝑣2,…,𝑣𝑛$v_1,v_2,\dots ,v_n$ is defined as the number of indices 𝑖$i$ (1≤𝑖≤𝑛$1\le i\le n$) such that 𝑣1+𝑣2+…+𝑣𝑖=0$v_1+v_2+\dots +v_i=0$.

You are given an array 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ of length 𝑛$n$. You can perform the following operation multiple times:

• select an index 𝑖$i$ (1≤𝑖≤𝑛$1\le i\le n$) such that 𝑎𝑖=0$a_i=0$;
• then replace 𝑎𝑖$a_i$ by an arbitrary integer.

What is the maximum possible score of 𝑎$a$ that can be obtained by performing a sequence of such operations?

Input

Each test contains multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$) — the number of test cases.

The first line of each test case contains one integer 𝑛$n$ (1≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$) — the length of the array 𝑎$a$.

The second line of each test case contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (−109≤𝑎𝑖≤109$-{10}^9\le a_i\le {10}^9$) — array 𝑎$a$.

It is guaranteed that the sum of 𝑛$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, print the maximum possible score of the array 𝑎$a$ after performing a sequence of operations.

Note

In the first test case, it is optimal to change the value of 𝑎2$a_2$ to −2$-2$ in one operation.

The resulting array 𝑎$a$ will be [2,−2,1,−1,0]$[2,-2,1,-1,0]$, with a score of 3$3$:

• 𝑎1+𝑎2=2−2=0$a_1+a_2=2-2=0$;
• 𝑎1+𝑎2+𝑎3+𝑎4=2−2+1−1=0$a_1+a_2+a_3+a_4=2-2+1-1=0$;
• 𝑎1+𝑎2+𝑎3+𝑎4+𝑎5=2−2+1−1+0=0$a_1+a_2+a_3+a_4+a_5=2-2+1-1+0=0$.

In the second test case, it is optimal to change the value of 𝑎3$a_3$ to −2000000000$-2000000000$, giving us an array with a score of 1$1$.

In the third test case, it is not necessary to perform any operations.