ASCII 미로

크기가 m x n인 격자 판에 1 x 1 조각들이 하나씩 놓여 있다. 각 조각에는 세 종류 중 하나의 무늬가 그려져 있으며, 조각은 자기 칸 안에서만 회전할 수 있고 다른 칸으로 옮길 수는 없다.

조각의 종류는 다음과 같다.

• 빈 조각: 선이 없으며 경로에 사용할 수 없다.
• 직선 조각: 가운데 줄이 아래처럼 ***로 그려져 있고, 회전하면 서로 마주 보는 두 변을 잇는다.

   ***   

• 모서리 조각: 아래 모양처럼 인접한 두 변을 잇고, 네 방향으로 회전할 수 있다.

   **  * 

초기 격자가 주어질 때, 조각들을 회전해서 왼쪽 위 칸의 어떤 변에서 시작해 오른쪽 아래 칸의 어떤 변으로 끝나는 하나 이상의 꺾은선 경로를 만들 수 있는지 판단해야 한다. 경로는 빈 조각을 지날 수 없고, 같은 칸을 두 번 사용할 수 없다.

첫 줄에는 테스트 케이스 수 c가 주어진다.

각 테스트 케이스는 먼저 두 정수 m과 n으로 시작하며, 이는 격자의 행과 열 개수이다. 이어서 4m + 1줄에 걸쳐 현재 격자의 ASCII 그림이 주어진다. 그림에는 +, -, |, *, 공백 문자가 사용된다.

각 격자는 m x n <= 64를 만족한다.

각 테스트 케이스마다 원하는 경로를 만들 수 있다면, 먼저 경로에 사용하는 칸 수가 가장 적은 경로 하나를 입력과 같은 격자 형식으로 출력한다. 그런 경로가 여러 개라면 아무 것이나 출력해도 된다. 경로에 포함되지 않는 칸은 모두 빈칸으로 출력한다.

그 뒤에 Number of solutions: X 형식으로 가능한 서로 다른 경로의 개수 X를 출력한다. 경로를 만들 수 없다면 격자는 출력하지 않고 이 줄만 출력한다.