Given a binary array. Find the minimum number of swap operations to be performed such that the Bitwise $AND$ of any subarray of size > 1 is equal. If it can't be done, print $-1$. Swap can be defined as interchanging array values at any two indices $i$ and $j$.

Input:

The first line contains $T$, the number of test cases

The first line of each test case contains $N$, the number of elements in the array

The second line of each test case contains $N$ integers $(0 \leq a[i] \leq 1)$

Output:

Print $T$ lines

Each line should contain the answer for that test case

Constraints :

$1 \leq T \leq 10^3$

$1 \leq N \leq 10^5$

$0 \leq a[i] \leq 1$

The sum of $N$ over all test cases does not exceed $10^5$