On his way home after a hectic day full of lab works, Tim found a sequence $a_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 $1\leq i,j\leq n$ satisfying $|i-j|=1$ (the indices are adjacent) and add $a_i$ to $a_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~ (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~(1\leq n\leq 100)$ denoting the number of elements in the sequence. The next line contains $n$ space separated integers $a_1,a_2,\ldots,a_n$ where $1\leq a_i\leq 100$ for each valid $i$.

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$ instead.

Sample

Input

Output

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 $a_1$ to $a_2$ and add $a_4$ to $a_3$. Then the sequence becomes $[1,3,3,1]$ whose product is $9$, an odd number. We can show that it is not possible to make fewer than $2$ moves.

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

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