Ben 是一位出色的电子游戏设计师，他正在为即将推出的增强现实手机游戏设计地图。最近，他创建了一张地图，该地图由 $R$ 行 $C$ 列的矩阵表示。地图由一些表示空地的 . 字符、一些表示不可通行墙壁的 # 字符、一个表示起点位置的 S 以及一个表示终点位置的 F 组成。例如，地图可能如下所示：

#############
#S..#..##...#
###.##..#.#F#
#...##.##.###
#.#.........#
#############

在 Ben 的游戏中，路径是指从一个单元格移动到另一个单元格的一系列步骤（上、下、左或右），且不能穿过任何不可通行的墙壁。

Ben 认为一张“好”的地图应具备以下属性：

• 任意两个空地之间（包括起点和终点）都存在一条路径。
• 为了保持结构完整性，不可通行的墙壁必须在边上相连，而不能仅仅在角上相连。对于地图中的每个 $2 \times 2$ 区域，如果该区域恰好包含两堵墙，那么这两堵墙必须位于同一行或同一列。换句话说，不存在墙壁呈以下两种配置之一的 $2 \times 2$ 区域：

#.  .#
.#  #.

• 边界仅由不可通行的墙壁组成。如果一个单元格位于最上行、最下行、最左列或最右列，则该单元格被视为边界的一部分。

最短路径的距离是从起点到达终点所需的最少步数。例如，在上述示例中，最短路径需要 17 步。

作为一名聪明的地图制作者，Ben 意识到他创建的地图对于他的朋友来说太难了。他希望通过移除一些不可通行的墙壁来降低难度。具体来说，他想知道是否可以通过移除地图中零个或多个不可通行的墙壁，使得从起点到终点的最短路径恰好为 $D$ 步，并且生成的地图仍然是“好”的。注意，仅仅找到一条长度为 $D$ 的路径是不够的；$D$ 必须是该地图中从起点到终点的最短路径长度。

例如，如果 $D = 15$，我们可以移除终点正下方的不可通行墙壁，从而得到一个好的解决方案。

#############
#S..#..##...#
###.##..#.#F#
#...##.##.#.#
#.#.........#
#############

如果 $D = 5$，则无解。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含三个空格分隔的整数 $R$、$C$ 和 $D$：地图的行数、列数，以及在移除部分墙壁后，从起点到终点的最短路径所需的步数。接下来的 $R$ 行，每行包含 $C$ 个字符（.、#、S 或 F），表示 Ben 的地图。

保证给定的地图符合题目描述的“好”的定义。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 为 POSSIBLE 或 IMPOSSIBLE，取决于是否可以通过移除若干墙壁使得最短路径长度恰好为 $D$ 且地图依然是“好”的。如果可能，再输出 $R$ 行，每行包含 $C$ 个字符，表示新地图。在输出中，将移除的墙壁（如果有）对应的 # 字符替换为 . 字符。

如果存在多种解决方案，输出其中任意一种即可。

数据范围

内存限制：1 GB。 $1 \le T \le 100$。 每个测试用例恰好包含一个 S 和一个 F。 输入文件大小不超过 3MB。

子任务 1

时间限制：20 秒。 $3 \le R \le 40$。 $3 \le C \le 40$。 $1 \le D \le 1600$。

子任务 2

时间限制：20 秒。 $3 \le R \le 1000$。 $3 \le C \le 1000$。 $1 \le D \le 10^6$。

注意：大型数据集的输出可能会超过 Code Jam 通常的输出大小限制，但你可以正常上传。

样例

样例输入 1

3
6 13 15
#############
#S..#..##...#
###.##..#.#F#
#...##.##.###
#.#.........#
#############
5 8 3
########
#S.....#
####...#
#F.....#
########
4 10 11
##########
#S#...#.F#
#...#...##
##########

样例输出 1

Case #1: POSSIBLE
#############
#S..#..##...#
###.##..#.#F#
#...##.##.#.#
#.#.........#
#############
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
##########
#S#...#.F#
#...#...##
##########

说明

样例输出展示了针对样例测试用例的一组答案。其他答案也可能是正确的。

样例 #1 是题目描述中的例子。

在样例 #2 中，可以通过移除墙壁使最短路径距离变为 2 或 4。然而，无法使最短路径距离恰好为 3。

在样例 #3 中，最短路径初始即为 11 步，因此无需降低地图难度。