Checkerboard Matrix (Large)

When she is bored, Mija plays with matrices. She tries to turn one matrix into another using as few moves as possible. For Mija, one move is swapping two rows of the matrix or swapping two columns of the matrix.

Today Mija has a very special matrix $M$. $M$ is a $2N \times 2N$ matrix whose entries are all 0 or 1. Mija wants to turn $M$ into a checkerboard matrix, a matrix whose entries alternate between 0 and 1 along every row and along every column. Find the minimum number of moves that turns $M$ into a checkerboard matrix.

The first line contains the number of test cases $T$. $T$ test cases follow. Each test case starts with a line containing a single integer $N$. The next $2N$ lines each contain $2N$ characters, which are the rows of $M$. Each character is 0 or 1.

Limits

• $1 \le T \le 100$
• $1 \le N \le 10^3$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of row swaps and column swaps that turns $M$ into a checkerboard matrix. If $M$ cannot be turned into a checkerboard matrix, print IMPOSSIBLE in place of $y$.

In the first sample case, $M$ is already a checkerboard matrix.

In the second sample case, Mija swaps columns 1 and 2 and then swaps rows 1 and 2 to get a checkerboard matrix.

In the third sample case, no sequence of moves works because the matrix does not have enough ones.