시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2 2 2 100.000%

문제

Doctor Nefario is leaving Gru because he misses being evil. While he is packing and preparing to leave, boxes become scattered all over the laboratory floor. In fact, there are so many boxes that minions may no longer be able to cross the room!

Your goal is to determine which parts of the lab minions can still reach. In particular you want to find whether minions can cross the room from the top left corner to the bottom right corner. Minions can only make 90 degree turns. I.e., they may move up, down, left, or right one location at a time, but not diagonally.

In the example above, minions need to cross a room of height 4 and width 3. Three boxes are scattered in the room. Minions start from the top left corner and try to reach the bottom right corner, making only 90 degree turns. It turns out that minions can reach every part of the room except the top right corner.

입력

The first line of the input file contains the number of test cases. Each case has the following format. First, a line containing the height H and width W of the room. Next, a sequence of H lines, each of containing W characters. Each character is either ‘X’ (occupied) or ‘O’ (clear).

출력

The output is the layout of the room for each test case, where locations are marked as ‘M’ if it can be reached by minions, followed by one of the the following lines: ”Minions can cross the room” or ”Minions cannot cross the room”.

예제 입력 1

2
4 3
OXO
OOX
XOO
OOO
4 3
OOO
OOX
OXO
XOO

예제 출력 1

Case: 1
+---+---+---+
| M | X |   |
+---+---+---+
| M | M | X |
+---+---+---+
| X | M | M |
+---+---+---+
| M | M | M |
+---+---+---+
Minions can cross the room 
Case: 2
+---+---+---+
| M | M | M |
+---+---+---+
| M | M | X |
+---+---+---+
| M | X |   |
+---+---+---+
| X |   |   |
+---+---+---+
Minions cannot cross the room