미니언의 이동

네파리오 박사가 다시 악당이 되고 싶어서 그루를 떠나려 한다. 박사가 짐을 싸는 동안 연구실 바닥 곳곳에 상자가 흩어졌다. 상자가 너무 많아서 미니언이 방을 가로지르지 못할 수도 있다.

미니언이 아직 갈 수 있는 칸이 어디인지 알아내야 한다. 특히 왼쪽 위 칸에서 출발해 오른쪽 아래 칸까지 갈 수 있는지 판정한다. 미니언은 90도 회전만 하므로 한 번에 위, 아래, 왼쪽, 오른쪽으로 한 칸씩만 움직이고 대각선으로는 움직이지 않는다. 상자가 놓인 칸에는 들어갈 수 없다.

그림의 방은 높이가 4, 너비가 3이고 상자 세 개가 놓여 있다. 미니언은 왼쪽 위 칸에서 출발해 오른쪽 아래 칸으로 가려 한다. 이 방에서는 오른쪽 위 칸을 뺀 모든 칸에 갈 수 있다.

출발 칸에 상자가 놓여 있으면 미니언은 어느 칸에도 갈 수 없다.

첫 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스의 첫 줄에는 방의 높이 H와 너비 W가 공백으로 구분되어 주어진다. 이어지는 H개의 줄에는 각각 W개의 문자가 주어진다. 각 문자는 상자가 놓인 칸을 뜻하는 X이거나 빈 칸을 뜻하는 O이다.

각 테스트 케이스마다 먼저 Case: k를 출력한다. k는 1부터 시작하는 테스트 케이스 번호다.

그다음 줄부터 방의 상태를 표로 출력한다. 가로줄을 먼저 출력하고, 방의 각 행마다 칸 줄과 가로줄을 차례로 출력한다. 따라서 가로줄은 H+1개, 칸 줄은 H개다.

• 가로줄은 +로 시작하고 그 뒤에 ---+를 W번 반복한 문자열이다.
• 칸 줄은 |로 시작하고, 왼쪽 칸부터 차례로 공백 한 개, 칸 문자 한 개, 공백 한 개, |를 붙인 문자열이다.
• 칸 문자는 미니언이 갈 수 있는 칸이면 M, 상자가 놓인 칸이면 X, 빈 칸이지만 미니언이 갈 수 없으면 공백 한 개다.

표 다음 줄에는 미니언이 오른쪽 아래 칸에 갈 수 있으면 Minions can cross the room을, 갈 수 없으면 Minions cannot cross the room을 출력한다.

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