척의 도전

척의 도전은 격자 모양의 타일로 이루어진 미로에서 플레이어가 길을 찾아가는 게임이다. 플레이어는 도중에 얻은 열쇠로 열 수 있는 문을 만날 수도 있다. 미로의 출구에 도달하려면 반드시 열어야 하는 문의 최소 개수를 구하는 프로그램을 작성하라.

규칙

• 대각선으로 맞닿은 칸은 인접한 것으로 보지 않는다. 상하좌우로 인접한 칸만 고려한다.
• 플레이어는 입구 칸에서 미로를 시작한다.
• 플레이어는 현재 방문 중인 칸과 상하좌우로 인접하고 통과 가능한 칸만 방문할 수 있다.
• 문은 대응하는 열쇠('A'는 'a', 'B'는 'b'처럼 짝을 이룬다)가 있는 칸을 방문하기 전까지 통과할 수 없다.
• 처음에는 불안정한 바닥을 통과할 수 있다. 다만 플레이어가 불안정한 바닥을 떠나 다른 종류의 칸을 방문하면 그 바닥은 통과할 수 없게 된다.
• 불안정한 바닥이 통과할 수 없게 되면, 인접한 불안정한 바닥도 모두 통과할 수 없게 된다.
• 미로의 바깥 가장자리는 통과할 수 없는 벽이다.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 50$)가 주어진다. 각 테스트 케이스는 두 정수 $R$과 $C$ ($4 \le R, C \le 50$)가 적힌 줄로 시작한다. 이어지는 $R$개의 줄에는 미로를 나타내는 $C$개의 문자가 한 줄씩 주어진다. 미로에는 위 표에 있는 문자만 나타난다.

각 테스트 케이스마다 출구에 도달하기 위해 열어야 하는 문의 최소 개수를 한 줄에 출력한다. 출구에 도달할 수 없으면 "Impossible"을 출력한다.