Алена собирает необычный пазл. Она делает это в течение \(n\) дней следующим образом:
- В первый день она начинает с того, что кладет центральный кусочек в центр стола.
- В каждый следующий день она кладет определенное количество кусочков вокруг центрального кусочка по часовой стрелке, всегда полностью завершая каждый квадратный слой перед началом нового.
Так, она ставит первые \(14\) кусочков в следующем порядке:
Цвета обозначают слои. Третий слой еще не завершен. Алена счастлива, если в конце дня собранная часть головоломки не имеет начатых, но не завершенных слоев. Вам дано количество кусочков, которые она кладет в каждый из дней. Найдите количество дней, когда Алена счастлива.
Выходные данные
Для каждого набора входных данных выведите одно целое число: количество дней, когда Алена счастлива.
Примечание
В первом наборе входных данных в единственный день Алена завершает единственный слой.
Во втором наборе входных данных в первый день Алена завершает первый слой, а во второй день она завершает второй слой.
В третьем наборе входных данных она завершает второй слой за несколько дней.
В четвертом наборе входных данных она завершает второй слой и сразу же начинает следующий в тот же день, поэтому она не будет счастливой в этот день. Она счастлива только в первый и последний дни.
В пятом наборе Алена счастлива в первый, четвертый и последний дни.
Примеры
| № | Входные данные | Выходные данные |
|
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
2
2
2
3
|