Random Access Emotions

题目描述

葵很想拥有一个稳定的情绪。

葵预测了她接下来 $n$ 天的心情变动。具体而言，她有一个序列 $\{a_i\}$，她预测她第 $i$ 天的心情会等于 $a_1 + a_2 + \ldots + a_i$。

这个序列中有一些元素等于 $0$。如果 $a_i = 0$，那么她可以任意控制第 $i$ 天的心情变化量。换言之，她可以将序列中等于 $0$ 的元素修改为任意整数（或者保持其不变）。

葵认为，如果某一天她的心情等于 $0$，那么她当天的情绪是稳定的。她想知道，通过修改序列中的元素，她最多可以有多少天情绪稳定。

输入格式

输入第一行一个整数 $T$。

接下来 $T$ 组数据，每组第一行一个整数 $n$。

第二行是 $n$ 个整数 $a_i$，表示她接下来几天的心情变动。

输出格式

对每组测试输出一个整数，代表这 $n$ 天里心情稳定的最多天数。

数据范围

• 对于 $30\%$ 的数据，$a_i \neq 0$，$n \leq 100$；
• 对于 $60\%$ 的数据，$n \leq 100$；
• 对于 $100\%$ 的数据，$1 \leq T \leq 10^4$，$1 \leq n, \sum n \leq 2 \cdot 10^5$，$-10^9 \leq a_i \leq 10^9$。

样例数据 1

输入：

5
3
1000000000 1000000000 0
5
2 0 1 -1 0
9
1 0 0 1 -1 0 1 0 -1
8
3 0 2 -10 10 -30 30 0
4
0 0 0 0

输出：

1
3
5
4
4

备注

本题为降级模式，仅提供题面和 1 组样例数据。