给你一个长度为 $n$ 的数组 $a[0 \ldots n-1]$，数组由非负整数构成。注意数组下标从 $0$ 开始。

如果数组中每个位置的下标的奇偶性与该位置元素的奇偶性相同，则称该数组为 好数组。更严格地说，若对所有 $i$（$0 \le i \le n-1$）都有：

则该数组为好数组，其中 $x \bmod 2$ 表示 $x$ 除以 $2$ 的余数。

例如，数组 $[0,5,2,1]$ 和 $[0,17,0,3]$ 是好数组；数组 $[2,4,6,7]$ 是坏数组，因为当 $i=1$ 时：

二者奇偶性不同。

你可以进行如下操作：一次操作中，任选数组中的两个元素并交换它们（不要求相邻）。

请你求出将数组变成好数组所需的最少交换次数；如果无法做到，输出 $-1$。

输入格式

第一行一个整数 $t$（$1 \le t \le 1000$），表示测试用例数量。

每个测试用例包含：

• 第一行一个整数 $n$（$1 \le n \le 40$），表示数组长度；
• 第二行 $n$ 个整数 $a_0,a_1,\ldots,a_{n-1}$（$0 \le a_i \le 1000$），表示初始数组。

输出格式

对每个测试用例输出一行一个整数：将数组变为好数组的最少交换次数；若不可能则输出 $-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