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

Вам дана последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$. Найдите минимальное количество элементов, которое нужно удалить из последовательности, чтобы после удаления сумма любых $$$2$$$ соседних элементов была четна.

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2,\dots,a_n$$$ ($$$1\leq a_i\leq10^9$$$) — элементы последовательности.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — минимальное количество элементов, которое нужно удалить из последовательности, чтобы сумма никаких $$$2$$$ последовательных элементов не была четна.

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

В первом примере после удаления $$$3$$$ последовательность становится равна $$$[2,4,6,8]$$$. Пары соседних элементов в этой последовательности — $$$\{[2, 4], [4, 6], [6, 8]\}$$$. Теперь каждая пара соседних элементов дает четную сумму. Поэтому достаточно удалить $$$1$$$ элемент, чтобы удовлетворить условию.