어둠 속의 하산 (Large)

문제

에베레스트 산 사면에 있다. 얼어 죽기 전에 몸을 피할 곳을 찾아야 하는데, 주위는 어둡다.

다행히 산의 지형은 미리 외워 두었다. 지형은 격자이고, 지나갈 수 없는 칸이 있고, 하룻밤 쉴 수 있는 굴이 있는 칸도 있다. 문제는 자신이 어느 칸에 있는지 모른다는 점이다. 경사가 급해서 위로는 올라갈 수 없고, 왼쪽, 오른쪽, 아래로만 한 칸씩 움직인다.

지형의 예는 다음과 같다. .은 지나갈 수 있는 칸, #은 지나갈 수 없는 칸, 숫자는 굴이다.

######
##...#
#..#.#
#...##
#0#..#
####1#
######

어두우니 계획을 따라 움직인다. 계획은 왼쪽, 오른쪽, 아래 중 한 방향으로 한 칸 움직이라는 지시를 차례로 늘어놓은 것이다. 지시가 가리키는 칸이 지나갈 수 있는 칸이거나 굴이면 그 지시를 따르고, 지나갈 수 없는 칸이면 그 지시를 무시한다. 어느 쪽이든 다음 지시로 넘어가고, 계획의 마지막 지시까지 이렇게 수행한다.

하산하려면 각 굴 $C$ 에 대해 다음 두 가지를 알아야 한다.

굴 $C$ 에 도달할 수 있는 출발 칸은 어디인가? 이런 칸의 집합을 $S_C$ , 그 개수를 $n_C$ 라고 한다.
$S_C$ 에 속한 어느 칸에서 출발해도 마지막에 굴 $C$ 에 서 있게 되는 계획이 하나라도 있는가? 있으면 그 굴을 lucky라고 한다.

계획을 수행하는 동안 굴 여러 개를 지나칠 수도 있다. 중요한 것은 모든 지시를 끝낸 뒤에 서 있는 칸뿐이고, 도중에 지나친 굴은 상관없다.

위 예에서 굴 0은 lucky다. 굴 0에 도달할 수 있는 칸은 자기 자신을 포함해 9개이고, 왼쪽, 왼쪽, 아래, 아래, 왼쪽, 아래 순서로 움직이는 계획을 따르면 그 9개 칸 어디서 출발해도 굴 0에서 끝난다.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트 케이스의 첫 줄에는 지형의 행 개수 $R$ 과 열 개수 $C$ 가 주어진다.

이어서 $R$ 개의 줄에 각각 $C$ 개의 문자가 주어져 지형을 나타낸다. 위 예와 같이 #은 지나갈 수 없는 칸, .은 지나갈 수 있는 칸이고, 숫자 0부터 9까지는 굴이다. 굴이 있는 칸도 지나갈 수 있다.

출력

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

그 다음 0번 굴부터 번호가 커지는 순서로 각 굴 $C$ 에 대해 C: nC LC 형식으로 한 줄씩 출력한다. $C$ 는 굴 번호, $n_C$ 는 그 굴에 도달할 수 있는 칸의 개수이고, $L_C$ 는 그 굴이 lucky면 Lucky, 아니면 Unlucky다.

제한

굴은 1개 이상 10개 이하다.
굴이 $d$ 개면 각 굴에 숫자 $0, 1, \dots, d-1$ 중 하나가 붙고, 두 굴의 숫자가 같은 경우는 없다.
지형의 경계에 있는 칸은 모두 지나갈 수 없다.
$1 \le T \le 20$
$3 \le R, C \le 60$

힌트

첫 번째 예제에서 lucky인 굴에 쓸 수 있는 계획은 다음과 같다.

굴 0은 빈 계획으로도 된다. 굴에 도달할 수 있다면 이미 굴에 서 있다.
굴 1은 오른쪽, 아래, 왼쪽 계획으로 된다.
굴 3은 오른쪽, 오른쪽, 왼쪽, 아래, 아래, 아래, 왼쪽 계획으로 된다.