本题没有可用的提交语言。

我们正在尝试在一个尺寸为$m \times n$的棋盘上构建一个迷宫。最初，棋盘的每个方格上放置了一块$1 \times 1$的薄胶合板，上面绘制了以下三种图案之一。

在构建迷宫时，我们可以任意旋转这些板块，但每个板块必须恰好覆盖棋盘的一个方格。不允许将板块移动到棋盘的其他方格。

给定一个初始覆盖板块的棋盘，我们希望以某种方式旋转这些板块，使得板块上的图案形成至少一条连接棋盘左上角方格和右下角方格的多边形曲线。下图展示了一个尺寸为$4 \times 6$的棋盘的初始状态，以及从该棋盘构建的一个迷宫，其中实现了上述目标。 你的任务是读取初始棋盘的描述，并判断是否可以通过旋转板块，使得图案形成一条连接左上角方格的某条边和右下角方格的某条边的路径。

输入格式

第一行输入包含一个整数$c$，表示测试用例的数量。每个测试用例的数据以两个整数$m$和$n$开头，分别表示棋盘的行数和列数。接下来的几行是棋盘的ASCII表示，初始放置的板块用字符+、-、|、*和空格表示。具体格式请参考样例输入。输入棋盘的大小满足$m \times n \leq 64$。

输出格式

对于每个测试用例，如果能够构建满足条件的迷宫，则以类似于输入格式的形式打印迷宫，其中路径用最少数量的方格表示（如果有多个这样的路径，任选其一即可）。不参与路径的方格应留空。如果无法构建迷宫，则不打印棋盘。在打印棋盘（如果有）之后，以下述格式打印迷宫问题的不同解的数量。

输入样例 1

1
4 6
+---+---+---+---+---+---+
|   |   |   |   |   |   |
|***|***|** |** |** |***|
|   |   | * | * | * |   |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
|   |** |** |***|** |** |
|   | * | * |   | * | * |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
|***|** |***|***|***|** |
|   | * |   |   |   | * |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
|** |   |***|   |** |** |
| * |   |   |   | * | * |
+---+---+---+---+---+---+

输出样例 1

+---+---+---+---+---+---+
|   |   |   |   |   |   |
|***|***|** |   |   |   |
|   |   | * |   |   |   |
+---+---+---+---+---+---+
|   |   | * |   |   |   |
|   |   | **|***|** |   |
|   |   |   |   | * |   |
+---+---+---+---+---+---+
|   |   |   |   | * |   |
|   |   |   |   | * |   |
|   |   |   |   | * |   |
+---+---+---+---+---+---+
|   |   |   |   | * |   |
|   |   |   |   | **|** |
|   |   |   |   |   | * |
+---+---+---+---+---+---+
Number of solutions: 2