Description

当感到无聊时，Mija 有时会玩一个关于矩阵的游戏。她尝试用尽可能少的操作次数将一个矩阵变换成另一个矩阵。对 Mija 来说，一次操作是指交换任意两行，或交换任意两列。

今天，Mija 有一个特别的矩阵 $\mathbf{M}$。这是一个 $2\mathbf{N} \times 2\mathbf{N}$ 的矩阵，其中每个元素都是 $0$ 或 $1$。Mija 决定尝试将 $\mathbf{M}$ 转换成一个棋盘矩阵，即矩阵中每一行与每一列的元素都按照 $0$ 和 $1$ 交替出现。

你能帮助 Mija 找出将 $\mathbf{M}$ 转换为棋盘矩阵所需的最少交换次数吗？如果无法转换成棋盘矩阵，请输出 "IMPOSSIBLE"。

Input Format

第一行是测试用例数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 个测试用例。

每个测试用例的第一行包含一个整数 $\mathbf{N}$。接下来的 $2\mathbf{N}$ 行，每行包含 $2\mathbf{N}$ 个字符（仅由 '0' 和 '1' 组成），表示矩阵 $\mathbf{M}$ 的一行。

Output Format

对于每个测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是最少的行交换与列交换次数之和；若无法转换成棋盘矩阵，输出 "IMPOSSIBLE"。

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

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

Hint

样例解释

• 样例 1 中，矩阵本身已经是棋盘矩阵，无需任何操作。
• 样例 2 中，Mija 可以先交换第 1 列和第 2 列，再交换第 1 行和第 2 行，即可得到棋盘矩阵，总共 2 次操作。
• 样例 3 中，矩阵中的 $1$ 数量不够，无法排成棋盘矩阵，因而输出为 "IMPOSSIBLE"。

限制条件

• $1 \leq \mathbf{T} \leq 100$

Small 数据集（4 分）

• 时间限制：60 3 秒
• $1 \leq \mathbf{N} \leq 10$

Large 数据集（9 分）

• 时间限制：120 5 秒
• $1 \leq \mathbf{N} \leq 10^3$

翻译由 ChatGPT-4o 完成