3.3 Bitwise Puzzle ðŸ§©

Score: 15pts

Time Limit: 2.00 sec

Discover the puzzle within a binary array! Your mission is to determine the minimum number of swaps needed to create a scenario where the Bitwise AND of any subarray with a size larger than 1 yields the same result. It's like solving a challenging game. However, if achieving this goal is impossible, you'll uncover the elusive -1. Get ready to swap, strategize, and uncover the solution to this intriguing binary array puzzle!

Constraints

1 <= T <= 10^3

1 <= N <= 10^5

0<=a[i]<=1

1 <= N <= 10^5

0<=a[i]<=1

Input Format

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 )

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 Format

Print T lines

Each line should contain the answer for that test case

Each line should contain the answer for that test case

Example 1

Input:

1

6

1 1 0 0 1 0

Output:

1

Explanation:

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.

1

6

1 1 0 0 1 0

Output:

1

Explanation:

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.