On his way home after a hectic day full of lab works, Tim found a sequence 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 satisfying (the indices are adjacent) and add to .
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?
The first line contains an integer denoting the number of test cases.
Each test case consists of two lines. The first line contains the integer denoting the number of elements in the sequence. The next line contains space separated integers where for each valid .
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 instead.
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 to and add to . Then the sequence becomes whose product is , an odd number. We can show that it is not possible to make fewer than moves. In the second case, no matter which one we add to the other, the product will not be odd. So we print . In the third case, the product is already an odd number , so we need zero moves. |