Minion Walk

Doctor Nefario is leaving Gru because he misses being evil. While he packs, boxes end up scattered all over the laboratory floor. There are so many boxes that the minions may no longer be able to cross the room.

Work out which parts of the lab the minions can still reach. In particular, decide whether they can get from the top left cell to the bottom right cell. Minions only make 90 degree turns, so they move one cell up, down, left, or right at a time, never diagonally. They cannot enter a cell that holds a box.

The room in the picture has height 4 and width 3, and three boxes sit in it. The minions start at the top left cell and try to reach the bottom right cell. In this room they can reach every cell except the top right one.

If a box sits on the starting cell, the minions cannot reach any cell at all.

The first line contains the number of test cases T.

The first line of each test case contains the height H and the width W of the room, separated by a space. The next H lines each contain W characters. Each character is X for a cell that holds a box, or O for an empty cell.

For each test case, first print Case: k, where k is the test case number starting from 1.

Then print the layout of the room as a table. Print a rule line first, then, for each row of the room, a cell line followed by another rule line. There are H+1 rule lines and H cell lines.

• A rule line starts with + and then repeats ---+ W times.
• A cell line starts with | and then, for each cell from left to right, appends one space, the cell character, one space, and |.
• The cell character is M if the minions can reach the cell, X if the cell holds a box, and a single space if the cell is empty but the minions cannot reach it.

On the line after the table, print Minions can cross the room if the minions can reach the bottom right cell, and Minions cannot cross the room otherwise.

• 1 ≤ T ≤ 100
• 1 ≤ H, W ≤ 20