题目描述

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

如果一个数组满足每个下标的奇偶性与该下标对应元素的奇偶性相同，则称该数组为“好数组”。更正式地说，对于所有 $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 \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$。

说明/提示

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

在第二个测试用例中，第一次操作需要交换下标为 $0$ 和 $1$ 的元素。

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

由 ChatGPT 4.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