B. Четный массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a[0 \ldots n-1]$$$ длины $$$n$$$, который состоит из неотрицательных целых чисел. Обратите внимание: массив нумеруется с нуля.

Назовём массив хорошим, если четность каждой позиции совпадает с четностью элемента в ней. Более формально, массив является хорошим, если для всех $$$i$$$ ($$$0 \le i \le n - 1$$$) выполнено равенство $$$i \bmod 2 = a[i] \bmod 2$$$, где $$$x \bmod 2$$$ — остаток от деления $$$x$$$ на 2.

Например, массивы [$$$0, 5, 2, 1$$$] и [$$$0, 17, 0, 3$$$] — хорошие, а массив [$$$2, 4, 6, 7$$$] — плохой, потому что для $$$i=1$$$ четность $$$i$$$ и $$$a[i]$$$ различна: $$$i \bmod 2 = 1 \bmod 2 = 1$$$, но $$$a[i] \bmod 2 = 4 \bmod 2 = 0$$$.

За один ход вы можете взять любые два элемента массива и поменять их местами (эти элементы не обязательно соседние).

Найдите минимальное количество ходов, за которое можно сделать массив $$$a$$$ хорошим, либо укажите, что это сделать невозможно.

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

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

Каждый набор начинается со строки, в которой записано целое число $$$n$$$ ($$$1 \le n \le 40$$$) — размер массива $$$a$$$.

Далее следует строка, содержащая $$$n$$$ целых чисел $$$a_0, a_1, \ldots, a_{n-1}$$$ ($$$0 \le a_i \le 1000$$$) — исходный массив.

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

Для каждого набора тестовых данных выведите одно целое число — минимальное количество ходов, за которое можно сделать заданный массив $$$a$$$ хорошим, или -1, если это сделать невозможно.

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

В первом наборе тестовых данных в первый ход можно поменять местами элементы на позициях $$$0$$$ и $$$1$$$, а во второй ход поменять местами элементы на позициях $$$2$$$ и $$$3$$$.

Во втором наборе тестовых данных в первый ход надо поменять местами элементы на позициях $$$0$$$ и $$$1$$$.

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