Such an Odd Product

Nirjhor Father Timm Memorial Prog...
Limits 1s, 512 MB

On his way home after a hectic day full of lab works, Tim found a sequence a1,a2,,ana_1,a_2,\ldots,a_n of positive integers on the overbridge beside NDC. He is a huge fan of odd products, so he decided to make the product of all these integers odd. In order to do that, Tim can make multiple moves of the following kind: choose a position in the array and add the number in that position to one of its adjacent positions.

Formally, in a move Tim can choose two indices 1i,jn1\leq i,j\leq n satisfying ij=1|i-j|=1 (the indices are adjacent) and add aia_i to aja_j.

Tim is tired, so he wants to know the minimum number of moves he has to make such that the product of all the numbers becomes odd. Can you help him?

Input

The first line contains an integer t (1t100)t~ (1\leq t\leq 100) denoting the number of test cases.

Each test case consists of two lines. The first line contains the integer n (1n100)n~(1\leq n\leq 100) denoting the number of elements in the sequence. The next line contains nn space separated integers a1,a2,,ana_1,a_2,\ldots,a_n where 1ai1001\leq a_i\leq 100 for each valid ii.

Output

For each test case, print the minimum number of moves required on a single line. If is not at all possible to make the product odd, print 1-1 instead.

Sample

InputOutput
4
4
1 2 2 1
2
4 6
3
1 1 1
10
4 7 8 6 4 6 7 3 10 2 
2
-1
0
7

In the first case, we can add a1a_1 to a2a_2 and add a4a_4 to a3a_3. Then the sequence becomes [1,3,3,1][1,3,3,1] whose product is 99, an odd number. We can show that it is not possible to make fewer than 22 moves.

In the second case, no matter which one we add to the other, the product will not be odd. So we print 1-1.

In the third case, the product is already an odd number 11, so we need zero moves.


Submit

Login to submit.

Statistics

100% Solution Ratio
Desh01Earliest, 3w ago
Desh01Fastest, 0.0s
Suvro_9192Lightest, 5.7 MB
Being_GoromShortest, 256B
Toph uses cookies. By continuing you agree to our Cookie Policy.