## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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 ${v}_{1},{v}_{2},\dots ,{v}_{n}$ is defined as the number of indices $i$ ($1\le i\le n$) such that ${v}_{1}+{v}_{2}+\dots +{v}_{i}=0$.

You are given an array ${a}_{1},{a}_{2},\dots ,{a}_{n}$ of length $n$. You can perform the following operation multiple times:

• select an index $i$ ($1\le i\le n$) such that ${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\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 2\cdot {10}^{5}$) — the length of the array $a$.

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}$) — array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $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 ${a}_{2}$ to $-2$ in one operation.

The resulting array $a$ will be $\left[2,-2,1,-1,0\right]$, with a score of $3$:

• ${a}_{1}+{a}_{2}=2-2=0$;
• ${a}_{1}+{a}_{2}+{a}_{3}+{a}_{4}=2-2+1-1=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 ${a}_{3}$ to $-2\phantom{\rule{thinmathspace}{0ex}}000\phantom{\rule{thinmathspace}{0ex}}000\phantom{\rule{thinmathspace}{0ex}}000$, giving us an array with a score of $1$.

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