Sau số pro vjp, ta lại tiếp tục có mảng pro vjp

Bạn sẽ được cho 1 mảng a[0…n−1] có n phần tử là các số nguyên dương. Biết rằng mảng bắt đầu từ vị trí (hay còn gọi là index) 0.

Một mảng được gọi là pro vjp khi và chỉ khi với tất cả các i (0 ≤ i ≤ n−1), ta có i mod 2= a[i] mod2, biết xmod2 được tính bằng công thức x − (x/2) ∗ 2 với x là số nguyên.

Ví dụ, mảng [0,5,2,1] và [0,17,0,3] được tính là pro vjp, và mảng [2,4,6,7] là không pro vjp, bởi vì tại index i=1, mảng này đã không thỏa điều kiện trên: i mod 2 = 1 mod 2 = 1, nhưng a[i] mod 2 = 4 mod 2 = 0.

Để biến một mảng từ pro vjp, chỉ cần chọn 2 phần tử bất kì của mảng và hoán đổi vị trí của chúng (không bắt buộc 2 phần tử này phải đứng cạnh nhau). Mỗi lần hoán đổi vị trí được tính là 1 lần henshin.

Tìm số lần henshin ít nhất để mảng a hóa pro vjp, hoặc in ra -1 nếu mảng này không thể hóa pro vjp.

Input
Dòng thứ nhất chứa số nguyên t (1≤t≤1000) — là số lượng test case. Sau đấy là t test cases theo sau.

Mỗi test case có 2 dòng, dòng thứ nhất chứa số nguyên n (1≤n≤40) — là số lượng phần tử mảng a.

Dòng tiếp theo chứa n các số nguyên dương a0,a1,…,an−1 (0≤ai≤1000) — mảng a ban đầu.

Output
Mỗi test case in ra 1 số nguyên — là yêu cầu đề bài.

Examples
Input

4
4
3 2 7 6
3
3 2 6
1
7
7
4 9 2 1 18 3 0

Output

2
1
-1
0

Note
Ở test case đầu tiên, lần henshin thứ nhất, bạn đổi vị trí phần tử ở index 0 và 1, và ở lần henshin thứ hai, 2 phần tử ở index 2 và 3 sẽ được hoán đổi với nhau.

Ở test case 2, lần henshin duy nhất, hoán đổi vị trí của 2 phần tử ở index 0 và 1.

Ở test case ba, mảng này bất lực trong việc hóa pro vjp.