CF 1367B - Even Array

You are given an array a[0…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≤i≤n−1) the equality imod2=a[i]mod2 holds, where xmod2

 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: imod2=1mod2=1, but a[i]mod2=4mod2=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.

Input

The first line contains a single integer t (1≤t≤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≤n≤40) — the length of the array a

.

The next line contains n integers a0,a1,…,an−1 (0≤ai≤1000) — the initial array.

Output

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

----------------------------------------------------------------------

给定一个长度为 n 的数组 a[0…n−1]，它由非负整数组成。 请注意，数组索引从零开始。

如果每个索引的奇偶校验与该索引处元素的奇偶校验匹配，则称该数组为良好数组。 更正式地说，如果对于所有 i 来说，数组就是好的

  (0≤i≤n−1) 等式 imod2=a[i]mod2 成立，其中 xmod2

  是 x 除以 2 的余数。

例如，数组 [0,5,2,1] 和 [0,17,0,3] 是好的，而数组 [2,4,6,7] 是坏的，因为对于 i=1，i 和 a[i] 的奇偶性不同：imod2=1mod2=1，但 a[i]mod2=4mod2=0。

一步操作中，您可以取出数组中的任意两个元素并交换它们（这些元素不一定相邻）。

求出可以使数组变好的最小移动次数，或者说这是不可能的。

输入

第一行包含一个整数 t (1≤t≤1000) — 测试中测试用例的数量。 然后是测试用例。

每个测试用例都以包含整数 n (1≤n≤40) 的行开始 — 数组 a 的长度

。

下一行包含 n 个整数 a0,a1,…,an−1 (0≤ai≤1000) — 初始数组。

输出

对于每个测试用例，输出一个整数 - 使给定数组良好的最小移动次数，如果不可能，则输出 -1

--------------------------------------

判断奇数索引上面偶数的数量和偶数索引上面奇数的数量是否一致，如果一致，那么可以组成，如果不一致，就输出-1；

下面是代码：