与樱子旅行后,幸介非常害怕,因为他忘记了他的编程作业。在这次作业中,老师给了他一个由$$$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