A. Все любят хорошие массивы!
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Массив $$$a$$$ называется хорошим, если для любой пары соседних элементов $$$a_i$$$ и $$$a_{i+1}$$$ ($$$1\le i \lt n$$$) имеют разную четность. В частности, массив размера $$$1$$$ всегда является хорошим.

Вам задан массив длины $$$n$$$.

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

Определите минимальное число операций, необходимое для того, чтобы сделать массив хорошим.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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 10^{9}$$$).

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

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

Пример
Входные данные
3
5
1 7 11 2 13
4
1 2 3 4
6
1 1 1 2 2 3
Выходные данные
2
0
3
Примечание

Рассмотрим первый набор входных данных. Выберем $$$2$$$-е и $$$3$$$-е числа и применим операций к ним. Массив, до этого равный $$$[1, \color{red}{7}, \color{red}{11}, 2, 13]$$$, станет равен $$$[1, \color{red}{77}, 2, 13]$$$. Затем выберем $$$1$$$-й и $$$2$$$-й элементы. Массив, равный $$$[\color{red}{1}, \color{red}{77}, 2, 13]$$$, станет равен $$$[\color{red}{77}, 2, 13]$$$. Таким образом, нам достаточно $$$2$$$ операций. Можно доказать, что меньшим числом операций обойтись нельзя.

Во втором наборе входных данных данный массив уже является хорошим. Поэтому нам нужно всего $$$0$$$ операций.