← 返回题目列表

Codeforces · 2033/D

D. 浩介的作业

中文机器翻译题面 查看原题

与樱子旅行后,幸介非常害怕,因为他忘记了他的编程作业。在这次作业中,老师给了他一个由$$$n$$$个整数组成的数组$$$a$$$,并要求他计算数组$$$a$$$中不重叠的段的数量,这样每个段都被认为是美丽的。

如果 $$$a_l + a_{l+1} + \dots + a_{r-1} + a_r=0$$$,则 $$$[l,r]$$$ 被认为是美丽的。

对于固定数组$$$a$$$,你的任务是计算不重叠的美丽片段的最大数量。

输入

输入的第一行包含数字 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。每个测试用例由 $$$2$$$ 行组成。

- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组的长度。
- 第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$-10^5 \le a_i \le 10^5$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3\cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数:不重叠的美丽片段的最大数量。

示例

输入 #1

3
5
2 1 -3 2 1
7
12 -4 4 43 -3 -5 8
6
0 -4 0 3 0 1

输出 #1

1
2
3