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≤a[i]≤1)
Output:
Print T lines
Each line should contain the answer for that test case
Constraints :
1≤T≤103
1≤N≤105
0≤a[i]≤1
The sum of N over all test cases does not exceed 105
We can swap indices 2 and 3. This way the array becomes 1 0 1 0 1 0.
Now the Bitwise AND of every subarray of size >1 is equal to 0.
It can be shown that this is the best possible answer.