어둠 속의 하산 (Small)

문제

에베레스트 산 사면에 있다. 얼기 전에 몸을 피할 곳을 찾아야 하는데, 하필 캄캄한 밤이다.

다행히 산의 지형은 이미 외워 두었다. 지형은 격자이고, 어떤 칸은 지나갈 수 없으며 어떤 칸에는 하룻밤을 지낼 수 있는 굴이 있다. 문제는 지금 자신이 어느 칸에 있는지 모른다는 점, 그리고 경사가 너무 급해서 위로는 올라갈 수 없다는 점이다. 할 수 있는 이동은 왼쪽, 오른쪽, 아래쪽으로 한 칸씩뿐이다.

지형은 다음처럼 적는다. '.'은 지나갈 수 있는 칸, '#'은 지나갈 수 없는 칸, 숫자는 굴이다. 굴이 있는 칸도 지나갈 수 있다.

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

앞이 보이지 않으니 미리 정한 계획대로 움직인다. 계획은 명령을 나열한 것이고, 각 명령은 왼쪽, 오른쪽, 아래쪽 중 한 방향으로 한 칸 움직이라는 뜻이다. 명령이 가리키는 칸을 지나갈 수 있으면 그 칸으로 움직인다. 지나갈 수 없으면 그 명령은 무시하고 제자리에 남는다. 어느 쪽이든 다음 명령으로 넘어가며, 계획의 마지막 명령까지 이렇게 진행한다.

하산을 위해 각 굴 $k$ 에 대해 두 가지를 알고 싶다.

굴 $k$ 에 도달할 수 있는 출발 칸은 어디인가? 그 칸의 집합을 $S_k$ , 칸의 개수를 $n_k$ 로 쓴다.
$S_k$ 의 어느 칸에서 출발해도 마지막에 굴 $k$ 에 서 있게 되는 계획이 하나라도 있는가? 있으면 굴 $k$ 를 행운의 굴이라고 한다.

계획을 따라가다가 다른 굴을 지나칠 수도 있다. 중요한 것은 모든 명령을 끝낸 뒤 서 있는 칸이고, 도중에 지나친 굴은 상관없다.

예를 들어 위 지형에서 굴 0은 행운의 굴이다. 굴 0에 도달할 수 있는 칸은 굴 0 자신까지 포함해 9개이고, 왼쪽, 왼쪽, 아래, 아래, 왼쪽, 아래 계획은 그 9개 칸 중 어디에서 시작하든 굴 0에서 끝난다.

입력

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

각 테스트 케이스의 첫 줄에는 지형의 행 수 $R$ 과 열 수 $C$ 가 주어진다. 이어지는 $R$ 개의 줄에는 각각 $C$ 개의 문자가 주어져 지형을 나타낸다. '#'은 지나갈 수 없는 칸, '.'은 지나갈 수 있는 칸, '0'부터 '9'까지의 숫자는 굴이다.

굴은 1개 이상 10개 이하다. 굴이 $d$ 개이면 굴의 번호는 $0, 1, \dots, d-1$ 이고, 번호가 같은 굴은 없다. 지형의 경계에 있는 칸은 모두 지나갈 수 없는 칸이다.

$1 \le T \le 20$

$3 \le R, C \le 10$

출력

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

그다음 번호가 작은 굴부터 차례로, 굴 $k$ 마다 한 줄에 굴 번호 $k$ , 콜론, 공백, $n_k$ , 공백, $L_k$ 를 출력한다. $n_k$ 는 굴 $k$ 에 도달할 수 있는 칸의 개수이고, $L_k$ 는 굴 $k$ 가 행운의 굴이면 Lucky, 아니면 Unlucky다.

힌트

예제 입력의 첫 번째 지형에서 행운의 굴에는 다음 계획을 쓸 수 있다.

굴 0: 빈 계획. 굴 0에 도달할 수 있는 칸은 굴 0뿐이므로 아무 명령도 하지 않으면 된다.
굴 1: 오른쪽, 아래, 왼쪽.
굴 3: 오른쪽, 오른쪽, 왼쪽, 아래, 아래, 아래, 왼쪽.