Minimum Operations to Achieve an Even Sum

You are given an array of n integers. Your task is to determine the minimum number of operations required to make the sum of the elements even, using the operation defined below.

Operation: In one operation, you are allowed to change the parity (i.e. odd to even or even to odd) of exactly one element. However, this operation can only be performed if the original array contains both an even number and an odd number. Otherwise, the operation cannot be performed.

Formally, let \(S = \sum_{i=1}^{n} a_i\) be the sum of the array. The answer is determined as follows:

• If \(S\) is even, no operation is needed (answer is 0).
• If \(S\) is odd and the array contains both even and odd numbers, one operation is sufficient (answer is 1).
• If \(S\) is odd and the array is homogeneous (all odd numbers), it is impossible to make \(S\) even using the allowed operation (answer is -1).

Note that the operation cannot be applied if the array does not initially have both parity types.

inputFormat

The input is given via stdin and has the following format:

T
n₁
a₁ a₂ ... aₙ₁
n₂
a₁ a₂ ... aₙ₂
...
nₜ
a₁ a₂ ... aₙₜ

Here, T is the number of test cases. For each test case, the first line contains a single integer n which is the number of elements in the array, followed by a line containing n space-separated integers.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of operations required to make the sum of the array even. If it is impossible, output -1.

The output should be printed to stdout.

## sample

3
5
1 2 3 4 5
4
2 4 6 8
3
1 3 5

1
0
-1

</p>