알맞은 열쇠

아주 오래전, 어느 피라미드의 입구는 2차원 자물쇠로 잠겨 있었다. 이 자물쇠는 정사각형 칸들이 규칙적인 행과 열로 배열된 평평한 나무판이며, 각 칸은 나무로 꽉 차 있거나 비어 있다.

이 자물쇠의 열쇠도 2차원이다. 열쇠는 자물쇠의 칸과 같은 크기의 단위 정사각형들을 이어 붙여 만든 하나의 연결된 조각이다. 열쇠는 자물쇠의 위쪽에서 아래로 끼워 넣는다. 열쇠는 마치 떨어지는 테트리스 조각처럼 움직인다. 즉, 아래로 내려가거나 좌우로 옆으로 미끄러지는 것만 가능하다. 위로 올라갈 수 없고, 회전할 수도 없다.

여러 개의 후보 열쇠 중 가장 깊이 들어가는 것부터 시험해 보려고 한다. 주어진 열쇠가 주어진 자물쇠에 얼마나 깊이 들어갈 수 있는지 구하는 프로그램을 작성하여라.

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

각 테스트 케이스는 다음과 같이 주어진다.

• 첫째 줄에 열쇠의 행 수 R과 열 수 C가 주어진다 (1 ≤ R, C ≤ 100).
• 다음 R개의 줄에는 각각 정확히 C개의 문자로 열쇠가 주어진다. #는 나무로 된 단위 정사각형을, .는 빈 공간을 나타낸다. 나무 칸들은 하나로 연결되어 있으며, 위쪽에서 임의의 개수의 행을 잘라내어도 연결 상태가 유지된다. 맨 위 행, 맨 아래 행, 맨 왼쪽 열, 맨 오른쪽 열에는 각각 적어도 하나의 나무 칸이 있다.
• 그다음 줄에 자물쇠의 깊이(행 수) D와 너비(열 수) W가 주어진다 (1 ≤ D ≤ 10000, 1 ≤ W ≤ 1000).
• 다음 D개의 줄에는 각각 정확히 W개의 문자로 자물쇠가 주어지며, #는 나무를, .는 빈 공간을 나타낸다.

각 테스트 케이스마다 한 줄을 출력한다.

깊이는 열쇠의 아래쪽 면과 자물쇠의 위쪽 면 사이의 거리로 측정하므로, 자물쇠 위에 얹혀 있는 열쇠의 깊이는 0이다. 아래로 내려가거나 좌우로 미끄러지는 움직임만으로 열쇠를 자물쇠 전체를 통과시켜 아래쪽으로 빼낼 수 있다면 다음을 출력한다.

The key can fall through.

그렇지 않다면, 열쇠가 도달할 수 있는 최대 깊이를 X라 할 때 다음을 출력한다.

The key falls to depth X.