数组 $$$v_1,v_2,\ldots,v_n$$$ 的分数定义为索引 $$$i$$$ ($$$1 \le i \le n$$$) 的数量,使得 $$$v_1+v_2+\ldots+v_i = 0$$$。
给定一个数组 $$$a_1,a_2,\ldots,a_n$$$,长度为 $$$n$$$。您可以多次执行以下操作:
- 选择索引 $$$i$$$ ($$$1 \le i \le n$$$) 使得 $$$a_i=0$$$;
- 然后将 $$$a_i$$$ 替换为任意整数。
通过执行一系列此类操作可以获得 $$$a$$$ 的最大可能分数是多少?
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — array $$$a$$$.
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在执行一系列操作后打印数组 $$$a$$$ 的最大可能分数。
示例
输入 #1
5 5 2 0 1 -1 0 3 1000000000 1000000000 0 4 0 0 0 0 8 3 0 2 -10 10 -30 30 0 9 1 0 0 1 -1 0 1 0 -1
输出 #1
3 1 4 4 5
注意
在第一个测试用例中,最好在一次操作中将 $$$a_2$$$ 的值更改为 $$$-2$$$。
生成的数组 $$$a$$$ 将为 $$$[2,-2,1,-1,0]$$$,得分为 $$$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$$$。
在第二个测试用例中,最好将 $$$a_3$$$ 的值更改为 $$$-2\,000\,000\,000$$$,从而为我们提供一个分数为 $$$1$$$ 的数组。
在第三个测试用例中,不需要执行任何操作。