Lucy has an array of boxes. The boxes are arranged in a straight line numbered to from left to right. Box contains chocolates.

Lucy thinks the arrangement looks beautiful if the boxes follow an even-odd repetitive pattern. That means the first box contains an even number of chocolates, the second box contains an odd number, the third box contains even, and so on. Here's a beautiful even-odd arrangement:

image

Lucy is asking you to make beautiful even-odd arrangements from her arrays of boxes. You are allowed to move some chocolates from one box to another. But you are not allowed to swap the boxes. In the final arrangement, every box must contain at least one chocolate.

Calculate the minimum number of chocolates you need to move to get an even-odd repetitive pattern. If it's not possible to get the desired pattern, print -1.

Input Format

The first line contains an integer denoting the number of queries.
The first line of each query contains an integer denoting the number of boxes.
The second line of each query contains space-separated integers describing the number of chocolates in each box.

Constraints

Subtask

  • for of the maximum score

Output Format

Print an integer describing the minimum number of chocolates you need to transfer to get the even-odd repetitive pattern. If it's not possible to get the desired pattern, print .

Sample Input 0

3
6
6 8 3 1 1 4
5
3 1 1 1 1
3
14 3 10

Sample Output 0

2
-1
0

Explanation 0

  • Query :

We have to transfer two chocolates to maintain the pattern. One possible way to transfer chocolates is shown below.

image

  • Query :

We can only transfer one chocolate from the first box. No matter what we do, we cannot get the even-odd pattern.

image

  • Query :

The boxes are already in the even-odd pattern so we don't need to transfer any chocolate.

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score