P16621 [GKS 2017 #C] X Squared

今年火爆的新玩具叫做 “X 平方”。它由一个 $N \times N$ 的方格盘组成，其中 $N$ 为奇数。恰好有 $2 \times N - 1$ 个格子上标有 X，其余格子为空白（用 `.` 字符表示）。在游戏的每一步中，玩家可以选择并交换两行格子，或者选择并交换两列格子。游戏的目标是让所有 X 都位于棋盘的的两条主对角线上，形成一个更大的 X 形状，如下面 $N = 5$ 的例子所示： ``` X...X .X.X. ..X.. .X.X. X...X ``` 你正准备玩你的 X 平方玩具，但它目前尚未达到目标状态。你怀疑你调皮的弟弟可能移动了一些格子，导致游戏无法完成。给定当前棋盘的配置，你能判断是否可能获胜吗？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行是一个整数 $N$，表示棋盘的大小。接着 $N$ 行，每行包含 $N$ 个字符；其中第 $i$ 行的第 $j$ 个字符，如果棋盘第 $i$ 行第 $j$ 列的格子上有 X，则为 `X`，否则为 `.`。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 为 `POSSIBLE`（如果可能获胜）或 `IMPOSSIBLE`（否则）。

在样例 #1 中，一种获胜策略为： 1. 交换第一行与中间行。 2. 交换最右侧列与中间列。 ``` ..X XX. X.X XX. -> ..X -> .X. XX. XX. X.X ``` 在样例 #2 中，没有任何操作序列能将棋盘变成所需的目标配置。 ### 限制条件 $1 \le T \le 100$。 $N \bmod 2 = 1$（$N$ 为奇数）。 棋盘中恰好有 $2 \times N - 1$ 个 X 和 $N^2 - 2 \times N + 1$ 个 `.`。 棋盘尚未处于题目描述中的目标状态。 **小数据集（测试集 1 – 可见）** $3 \le N \le 5$。 **大数据集（测试集 2 – 隐藏）** $3 \le N \le 55$。 翻译由 DeepSeek V4 Pro 完成