407919: GYM102942 B Make All Odd

You are given an array of $$$n$$$ integers. You want to make all the numbers in this array as odd. In one operation you can select two indices $$$i$$$ and $$$j$$$ $$$(i \neq j)$$$ and replace $$$a_i$$$ with $$$(a_i + a_j)$$$.

Find the minimum number of operations needed to make all the numbers odd. If there is no way to do it, then print $$$-1$$$.

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^{2})$$$ — the number of test cases in the input.

Then $$$t$$$ test cases follow.

The first line of the test case contains one integer $$$n$$$ $$$( 1 \leq n \leq 2\cdot10^{5} )$$$.

The second line of the test case contains $$$n$$$ space-separated integers $$$a_i$$$ $$$( 1 \leq a_i \leq 10^{6} )$$$$$$-$$$$$$a_i$$$ is the $$$i^{th}$$$ number.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2\cdot10^{5}(\sum n \leq 2\cdot10^{5})$$$.

For each test case, If it is impossible to make all the numbers odd then print $$$-1$$$, otherwise print the minimum number of operation needed to make all the numbers odd.

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

2
2
3
-1

In the first test

Operation 1: replace $$$a_2$$$ with $$$(a_1 + a_2)$$$. The new array is $$$a = [1, 5, 3, 2]$$$.

Operation 2: replace $$$a_4$$$ with $$$(a_3 + a_4)$$$. The new array is $$$a = [1, 5, 3, 5]$$$.

In the fourth test, it is impossible to make all the numbers as odd.