Minimum number of Flips

 Chef has an array 

A$A$ of length N$N$ consisting of 1$1$ and −1$-1$ only.

In one operation, Chef can choose any index i$i$ (1≤i≤N)$(1\le i\le N)$ and multiply the element Ai$A_i$ by −1$-1$.

Find the minimum number of operations required to make the sum of the array equal to 0$0$. Output -1 if the sum of the array cannot be made 0$0$.

Input Format

• First line will contain T$T$, number of test cases. Then the test cases follow.
• First line of each test case consists of a single integer N$N$ denoting the length of the array.
• Second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ denoting the array A$A$.

Output Format

For each test case, output the minimum number of operations to make the sum of the array equal to 0$0$. Output -1 if it is not possible to make the sum equal to 0$0$.

Constraints

• 1≤T≤100$1\le T\le 100$
• 2≤N≤1000$2\le N\le 1000$
• Ai=1$A_i=1$ or Ai=−1$A_i=-1$

Sample Input 1 

4
4
1 1 1 1
5
1 -1 1 -1 1
6
1 -1 -1 1 1 1
2
1 -1

Sample Output 1 

2
-1
1
0

Explanation

Test case 1$1$: The minimum number of operations required is 2$2$. In the first operation, change A3$A_3$ from 1$1$ to −1$-1$. Similarly, in the second operation, change A4$A_4$ from 1$1$ to −1$-1$. Thus, the sum of the final array is 1+1−1−1=0$1+1-1-1=0$.

Test case 2$2$: It can be proven that the sum of the array cannot be made equal to zero by making any number of operations.

Test case 3$3$: We can change A1$A_1$ from 1$1$ to −1$-1$ in one operation. Thus, the sum of the array becomes −1−1−1+1+1+1=0$-1-1-1+1+1+1=0$.

Test case 4$4$: The sum of the array is already zero. Thus we do not need to make any operations.