← 返回题目列表

Codeforces · 2047/A

A. 阿莉安娜和方形拼图

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

阿廖娜组装了一个不寻常的方形拼图。她通过以下方式在 $$$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 在第一天、第四天和最后几天都很高兴。