CF1367B.Even Array

You are given an array $a[0 \ldots n-1]$ of length $n$ which consists of non-negative integers. Note that array indices start from zero.

An array is called good if the parity of each index matches the parity of the element at that index. More formally, an array is good if for all $i$ ($0 \le i \le n - 1$) the equality $i \bmod 2 = a[i] \bmod 2$ holds, where $x \bmod 2$ is the remainder of dividing $x$ by 2.

For example, the arrays [$0, 5, 2, 1$] and [$0, 17, 0, 3$] are good, and the array [$2, 4, 6, 7$] is bad, because for $i=1$, the parities of $i$ and $a[i]$ are different: $i \bmod 2 = 1 \bmod 2 = 1$, but $a[i] \bmod 2 = 4 \bmod 2 = 0$.

In one move, you can take any two elements of the array and swap them (these elements are not necessarily adjacent).

Find the minimum number of moves in which you can make the array $a$ good, or say that this is not possible.

给你一个长度为 $n$ 的数组 $a[0 \ldots n-1]$，其中所有元素均为非负整数。注意：数组下标从 0 开始。

若数组中每个下标的奇偶性与其对应位置上元素的奇偶性一致，则称该数组为好数组。更准确地说，数组是好数组，当且仅当对所有 $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$ 变为好数组所需的最少操作次数；若不可能实现，则说明这一点。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases in the test. Then $t$ test cases follow.

Each test case starts with a line containing an integer $n$ ($1 \le n \le 40$) — the length of the array $a$.

The next line contains $n$ integers $a_0, a_1, \ldots, a_{n-1}$ ($0 \le a_i \le 1000$) — the initial array.

第一行包含一个整数 $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$）—— 表示初始数组。

For each test case, output a single integer — the minimum number of moves to make the given array $a$ good, or -1 if this is not possible.

对于每个测试用例，输出一个整数——使给定数组 $a$ 变为“好”的最小移动次数；如果无法实现，则输出 -1。

In the first test case, in the first move, you can swap the elements with indices $0$ and $1$, and in the second move, you can swap the elements with indices $2$ and $3$.

In the second test case, in the first move, you need to swap the elements with indices $0$ and $1$.

In the third test case, you cannot make the array good.

在第一个测试用例中，第一次操作可以交换索引为 $0$ 和 $1$ 的元素，第二次操作可以交换索引为 $2$ 和 $3$ 的元素。

在第二个测试用例中，第一次操作必须交换索引为 $0$ 和 $1$ 的元素。

在第三个测试用例中，无法使数组变为“好”数组。