Hey Google, 운전해 줘!

Google Assistant 팀과 Android Auto 팀은 음성 명령으로 운전할 수 있는 새로운 시제품 자동차를 공동으로 개발하고 있다. 초기 시제품은 자동차 시뮬레이터에 연결된 휴대전화를 통해 작동한다. 안타깝게도 초기 테스터 중 한 명이 휴대전화를 변기에 빠뜨려 마이크가 손상되었고, 이로 인해 새로운 기능을 사용하기가 더 어려워졌다. 이 기회를 놓치고 싶지 않은 테스터는 어떻게든 이 기능을 사용할 수 있도록 여러분의 도움을 원한다.

초기 시제품은 $\mathbf{R}$개의 행과 $\mathbf{C}$개의 열로 이루어진 단순한 격자에서 움직이며, 북쪽, 남쪽, 동쪽, 서쪽이라는 $4$개의 매우 간단한 음성 명령만 이해한다. 각 명령은 자동차가 해당 방향으로 정확히 한 칸 이동하도록 시도하게 한다. 하지만 마이크 문제로 인해 시스템이 북쪽과 남쪽을 서로 잘못 알아들을 수 있으며, 이와 별개로 동쪽과 서쪽도 서로 잘못 알아들을 수 있다. 즉, 북쪽 명령을 내리면 자동차가 북쪽이나 남쪽으로 움직일 수 있고, 남쪽 명령을 내리면 남쪽이나 북쪽으로 움직일 수 있으며, 마찬가지로 동쪽과 서쪽 명령 중 어느 것을 내려도 자동차가 동쪽이나 서쪽으로 움직일 수 있다. 모든 경우에 두 이동 선택지는 같은 확률로 발생할 수 있다($1/2$).

테스터는 각 칸이 벽이나 위험 요소를 포함하거나 비어 있도록 주행 격자를 구성했다. 명령에 따라 자동차가 벽이 있는 칸이나 격자 밖으로 이동하게 되는 경우, 자동차는 대신 아무것도 하지 않는다. 명령에 따라 자동차가 위험 요소가 있는 칸으로 이동하면, 자동차는 더 이상 어떤 명령도 실행할 수 없다.

테스터는 격자의 빈 칸 일부를 관심 출발점으로, 다른 일부를 관심 도착점으로 표시했다. 관심 출발점과 관심 도착점의 쌍은, 음성 명령을 통해 출발점에서 자동차를 운전하여 적어도 $1 - 10^{-{10^{100}}}$의 확률로 도착점에서 끝나게 하는 전략이 존재할 경우 주행 가능하다고 한다. 전략은 이전 명령들의 결과에 따라 어떤 명령을 내릴지와 언제 멈출지를 선택할 수 있다. 자동차가 위험 요소가 있는 칸으로 이동하면 움직임을 멈추므로 도착점에 도달할 수 없다는 점에 유의한다. 테스터는 주행 가능한 모든 쌍의 목록을 찾는 데 여러분의 도움을 원한다.

제한

시간 제한: 60초. 메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$. 모든 $i, j$에 대해, $\mathbf{G_{i,j}}$는 마침표(.), 해시 기호(#), 별표(*), 영문 소문자 또는 영문 대문자 중 하나이다. 모든 $i, j\}$에 대한 집합 $\{\mathbf{G_{i,j}}$에는 영문 소문자가 적어도 $1$개, 영문 대문자가 적어도 $1$개 포함된다. 각 소문자와 대문자는 모든 $\mathbf{G_{i,j}}$에서 최대 한 번 나타난다.

테스트 세트 1 (결과 공개)

$1 \le \mathbf{R} \le 20$. $1 \le \mathbf{C} \le 20$.

테스트 세트 2 (결과 비공개)

$1 \le \mathbf{R} \le 100$. $1 \le \mathbf{C} \le 100$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 격자의 행 수와 열 수를 나타내는 두 정수 $\mathbf{R}$과 $\mathbf{C}$이 포함된 줄로 시작한다. 이어서 각각 $\mathbf{C}$개의 문자로 이루어진 문자열을 포함하는 $\mathbf{R}$개의 줄이 주어진다. 이 줄들 중 $i$-번째 줄의 $j$-번째 문자 $\mathbf{G_{i,j}}$는 격자의 $i$-번째 행과 $j$-번째 열에 있는 칸을 다음과 같이 나타낸다.

• 마침표(.)는 관심 대상이 아닌 빈 칸을 나타낸다.

• 해시 기호(#)는 벽이 있는 칸을 나타낸다.

• 별표(*)는 위험 요소가 있는 칸을 나타낸다.

• 영문 소문자(a부터 z까지)는 관심 출발점인 빈 칸을 나타낸다.

• 영문 대문자(A부터 Z까지)는 관심 도착점인 빈 칸을 나타낸다.

각 테스트 케이스에 대해 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 (1부터 시작하는) 테스트 케이스 번호이고, 주행 가능한 쌍이 없다면 $y$은 NONE이다. 그렇지 않다면 $y$은 출발점 문자를 먼저, 도착점 문자를 나중에 배치하여 주행 가능한 모든 쌍을 나타내는 $2$자 문자열들을 알파벳순으로 공백으로 구분해 나열한 것이어야 한다.

예제 케이스 #1에서는 도착점에 도달할 때까지 서쪽 명령을 계속 반복하기만 하면 되는 전략을 사용할 수 있다. 매번 도착점에 도달할 확률은 $1/2$이고 같은 위치에 머무를 확률은 $1/2$이다. 따라서 $10^{101}$회 이하의 이동으로 도착점에 도달하지 못할 확률은 $2^{-10^{101}} \lt 10^{-10^{100}}$이다.

예제 케이스 #2에서는 예제 케이스 #1과 비슷한 전략을 사용하여 맨 위 행(1)의 어느 위치에서든 원하는 다른 위치로 자동차를 원하는 만큼 높은 확률로 이동시킬 수 있으며, 위에서 세 번째 행(2)의 벽이 아닌 모든 위치 사이에서도 마찬가지이다. 이와 유사하게 남쪽 명령을 사용하면 왼쪽에서 세 번째 열(3)의 벽이 아닌 위치 사이에서 자동차를 이동시킬 수 있다. a과 c 모두에서 (1)을 사용해 왼쪽에서 세 번째 열로 이동한 다음, (3)을 사용해 Y 바로 옆으로 이동하고, 이어서 (2)을 사용해 Y에 도달할 수 있으므로 aY과 cY은 둘 다 주행 가능하다. 하지만 세 번째 행에서 북쪽 또는 남쪽 명령을 안전하게 사용할 수 있는 곳은 세 번째 열뿐이며, 그 밖의 곳에서는 자동차가 위험 요소가 있는 칸으로 이동할 수 있다는 점에 유의한다. 따라서 자동차를 세 번째 행에서 네 번째 행으로 이동시킬 안전한 방법이 없으므로 aX과 cX은 주행 가능하지 않다. 그러나 b에서는 비슷한 전략을 사용해 자동차를 X로 이동시킬 수 있고, X에서는 북쪽 또는 남쪽 명령을 반복해서 사용하여 자동차를 Y로 이동시킬 수 있다. 이때 Y에 도달하면 멈추므로 위쪽의 위험 요소가 있는 칸으로 이동할 위험은 전혀 없다. 마지막으로 도착점 Z은 완전히 고립되어 있으므로 어떤 주행 가능한 쌍에도 포함될 수 없다.

예제 케이스 #3에서는 관심 출발점에서 관심 도착점으로 가는 모든 경로가 위험 요소가 있는 칸을 지나므로 이 쌍은 주행 가능하지 않다.

예제 케이스 #4에서는 관심 출발점 d에만 도착점 F에 도달할 수 있는 전략이 존재한다.