题目描述

今年火爆的新玩具叫做 “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（否则）。

2
3
..X
XX.
XX.
3
...
XXX
XX.

Case #1: POSSIBLE
Case #2: 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 完成