题目描述

When she is bored, Mija sometimes likes to play a game with matrices. She tries to transform one matrix into another with the fewest moves. For Mija, one move is swapping any two rows of the matrix or any two columns of the matrix.

Today, Mija has a very special matrix $\mathbf{M}$. $\mathbf{M}$ is a $2 \mathrm{~N}$ by $2 \mathrm{~N}$ matrix where every entry is either a 0 or a 1 . Mija decides to try and transform $\mathbf{M}$ into a checkerboard matrix where the entries alternate between 0 and 1 along each row and column. Can you help Mija find the minimum number of moves to transform $\mathbf{M}$ into a checkerboard matrix?

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case starts with a line containing a single integer: $\mathbf{N}$. The next $2 \mathrm{~N}$ lines each contain $2 \mathrm{~N}$ characters which are the rows of $\mathbf{M}$; each character is a 0 or 1 .

输出格式

For each test case, output one line containing "Case #x: $y$", where $\mathrm{x}$ is the test case number (starting from 1) and $y$ is the minimum number of row swaps and column swaps required to turn $\mathbf{M}$ into a checkerboard matrix. If it is impossible to turn $\mathbf{M}$ into a checkerboard matrix, $y$ should be "IMPOSSIBLE".

3
1
01
10
2
1001
0110
0110
1001
1
00
00

Case #1: 0
Case #2: 2
Case #3: IMPOSSIBLE

提示

Sample Explanation

In the first sample case, $\mathbf{M}$ is already a checkerboard matrix.

In the second sample case, Mija can turn $\mathbf{M}$ into a checkerboard matrix by swapping columns 1 and 2 and then swapping rows 1 and 2.

In the third sample case, Mija can never turn $\mathbf{M}$ into a checkerboard matrix; it doesn't have enough $1 \mathrm{~s}$.

Limits

• $1 \leq \mathrm{T} \leq 100$.

Small dataset(4 Pts)

• Time limit: 60 3 seconds.
• $1 \leq \mathrm{N} \leq 10$.

Large dataset(9 Pts)

• Time limit: 120 5 seconds.
• $1 \leq \mathrm{N} \leq 10^{3}$.