A. Алена и квадратный пазл
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алена собирает необычный пазл. Она делает это в течение $$$n$$$ дней следующим образом:

  • В первый день она начинает с того, что кладет центральный кусочек в центр стола.
  • В каждый следующий день она кладет определенное количество кусочков вокруг центрального кусочка по часовой стрелке, всегда полностью завершая каждый квадратный слой перед началом нового.

Так, она ставит первые $$$14$$$ кусочков в следующем порядке:

Цвета обозначают слои. Третий слой еще не завершен.

Алена счастлива, если в конце дня собранная часть головоломки не имеет начатых, но не завершенных слоев. Вам дано количество кусочков, которые она кладет в каждый из дней. Найдите количество дней, когда Алена счастлива.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$ — это количество кусочков, которые Алена собирает в $$$i$$$-й день.

Гарантируется, что в каждом наборе входных данных в конце $$$n$$$ дней нет незавершенных слоев.

Выходные данные

Для каждого набора входных данных выведите одно целое число: количество дней, когда Алена счастлива.

Пример
Входные данные
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
Примечание

В первом наборе входных данных в единственный день Алена завершает единственный слой.

Во втором наборе входных данных в первый день Алена завершает первый слой, а во второй день она завершает второй слой.

В третьем наборе входных данных она завершает второй слой за несколько дней.

В четвертом наборе входных данных она завершает второй слой и сразу же начинает следующий в тот же день, поэтому она не будет счастливой в этот день. Она счастлива только в первый и последний дни.

В пятом наборе Алена счастлива в первый, четвертый и последний дни.