Minimum Swaps to Make Array Beautiful

You are given T test cases. For each test case, you are given an integer N and an array of N integers. An array is called beautiful if the sum of its elements is even; i.e., if $$S \mod 2 = 0$$, where $$S$$ is the sum of the array.

The only allowed operation is to swap any two adjacent elements. Note that swapping adjacent elements does not alter the sum of the array. Therefore, if the sum is even, no operations are needed; if the sum is odd, it is impossible to make the array beautiful.

Your task is to determine the minimum number of swaps required to make the array beautiful. If the array is initially beautiful, output 0. Otherwise, output -1.

Input is read from stdin and output is written to stdout.

inputFormat

The input begins with an integer T representing the number of test cases. Each test case consists of two lines:

1. The first line contains an integer N, the number of elements in the array.
2. The second line contains N space-separated integers representing the elements of the array.

For example:

3
4
1 2 3 4
3
1 3 5
5
2 4 6 8 10

outputFormat

For each test case, output a single integer on a new line. The integer must be 0 if the sum of the array is even (i.e. the array is already beautiful), or -1 if the sum is odd (i.e. it is impossible to make the array beautiful).

For example, the sample output corresponding to the sample input above is:

0
-1
0

## sample

3
4
1 2 3 4
3
1 3 5
5
2 4 6 8 10

0
-1
0

</p>