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

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

給定一個(gè)長(zhǎng)度為 n 的數(shù)組 a[0…n?1]，它由非負(fù)整數(shù)組成。 請(qǐng)注意，數(shù)組索引從零開始。

如果每個(gè)索引的奇偶校驗(yàn)與該索引處元素的奇偶校驗(yàn)匹配，則稱該數(shù)組為良好數(shù)組。 更正式地說(shuō)，如果對(duì)于所有 i 來(lái)說(shuō)，數(shù)組就是好的

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

? 是 x 除以 2 的余數(shù)。

例如，數(shù)組 [0,5,2,1] 和 [0,17,0,3] 是好的，而數(shù)組 [2,4,6,7] 是壞的，因?yàn)閷?duì)于 i=1，i 和 a[i] 的奇偶性不同：imod2=1mod2=1，但 a[i]mod2=4mod2=0。

一步操作中，您可以取出數(shù)組中的任意兩個(gè)元素并交換它們（這些元素不一定相鄰）。

求出可以使數(shù)組變好的最小移動(dòng)次數(shù)，或者說(shuō)這是不可能的。

輸入

第一行包含一個(gè)整數(shù) t (1≤t≤1000) — 測(cè)試中測(cè)試用例的數(shù)量。 然后是測(cè)試用例。

每個(gè)測(cè)試用例都以包含整數(shù) n (1≤n≤40) 的行開始 — 數(shù)組 a 的長(zhǎng)度

。

下一行包含 n 個(gè)整數(shù) a0,a1,…,an?1 (0≤ai≤1000) — 初始數(shù)組。

輸出

對(duì)于每個(gè)測(cè)試用例，輸出一個(gè)整數(shù) - 使給定數(shù)組良好的最小移動(dòng)次數(shù)，如果不可能，則輸出 -1

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

判斷奇數(shù)索引上面偶數(shù)的數(shù)量和偶數(shù)索引上面奇數(shù)的數(shù)量是否一致，如果一致，那么可以組成，如果不一致，就輸出-1；

下面是代碼：