阿廖娜组装了一个不寻常的方形拼图。她通过以下方式在 $$$n$$$ 天内完成了此操作:
- 第一天,她首先将中央棋子放在桌子中央。
- 在第一天之后的每一天,她都会按顺时针顺序在中心棋子周围放置一定数量的棋子,总是在开始新的棋子之前完全完成每个方格层。
例如,她按以下顺序放置前 $$$14$$$ 块:
颜色表示层。第三层还没有完成。
如果在一天结束时拼图的组装部分没有任何已开始但未完成的层,Alyona 会很高兴。给出她每天组装的零件数量,求出阿廖娜快乐的天数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$),即天数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$, $$$a_1 = 1$$$),其中 $$$a_i$$$ 是 Alyona 在第 $$$i$$$ 天组装的件数。
在每个测试用例中保证在 $$$n$$$ 天结束时,没有未完成的层。
输出
对于每个测试用例,打印一个整数:Alyona 快乐的天数。
示例
输入 #1
5 1 1 2 1 8 5 1 3 2 1 2 7 1 2 1 10 2 7 2 14 1 10 10 100 1 1 10 1 10 2 10 2 10 1
输出 #1
1 2 2 2 3
注意
在第一个测试用例中,Alyona 在唯一一天完成了唯一的一层。
在第二个测试用例中,第一天,Alyona 完成了第一层,第二天,她完成了第二层。
在第三个测试用例中,她在几天内完成了第二层。
在第四个测试用例中,她完成了第二层,并在同一天立即开始下一层,因此,她那天不高兴。她只在第一天和最后几天感到高兴。
在第五个测试用例中,Alyona 在第一天、第四天和最后几天都很高兴。