어둠 속에서 내려가기

당신은 에베레스트산의 산비탈에 있다. 얼어붙기 전에 피난처를 찾아야 하는데, 어둠까지 깔렸다! 어떻게 해야 할까?

다행히도 당신은 이미 산의 지형을 외워 두었다. 산은 특정 칸들은 지나갈 수 없고 다른 칸들에는 밤을 보내며 쉴 수 있는 동굴이 있는 격자이다. 안타깝게도 당신은 자신이 어디에 있는지 모르며, 너무 가팔라서 위로 올라갈 수도 없다. 왼쪽, 오른쪽 또는 아래쪽으로만 이동할 수 있다.

다음은 지형의 예시이다. '.'은 지나갈 수 있는 칸을, '#'은 지나갈 수 없는 칸을, 숫자는 동굴을 나타낸다.

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

너무 어둡기 때문에, 당신은 일련의 지시로 이루어진 계획을 따라 이동한다. 각 지시는 왼쪽, 오른쪽 또는 아래쪽으로 한 칸 이동하라고 한다. 어떤 지시를 따르면 지나갈 수 있는 칸이나 동굴로 이동하게 되는 경우에는 그 지시를 따른다. 지나갈 수 없는 칸으로 이동하게 되는 경우에는 그 지시를 무시해야 한다. 어느 경우든 다음 단계로 계속 진행하며, 이런 식으로 전체 계획을 모두 수행할 때까지 진행한다.

하산에 도움을 받기 위해, 각 동굴 C에 관해 다음 두 가지를 알아내고자 한다.

• 어떤 칸에서 C에 도달할 수 있는가? 이 칸들의 집합을 $S_{C}$로, 그 개수를 $n_{C}$로 나타낸다.

• $S_{C}$의 어느 칸에서 시작해 따르더라도 동굴 C에서 끝나는 하나의 계획이 존재하는가? 그런 계획이 존재하면 그 동굴을 행운의 동굴이라고 한다.

계획을 따르는 동안 여러 동굴을 지나칠 수도 있음에 유의하라. 중요한 것은 도중에 어떤 동굴을 방문하는지가 아니라, 모든 단계를 수행한 뒤 어느 칸에서 끝나는지이다.

예를 들어 위 지형에서 동굴 0은 행운의 동굴이다. 이 동굴에 도달할 수 있는 칸은 동굴 자체를 포함해 9개이며, "왼쪽-왼쪽-아래쪽-아래쪽-왼쪽-아래쪽" 계획은 그 칸들 중 어느 칸에서 시작하더라도 동굴에서 끝난다.

제한

메모리 제한: 1GB. 시간 제한: 테스트 세트당 40초. 동굴은 1개 이상 10개 이하이다. 동굴이 d개라면 숫자 {0, 1, ..., d - 1}로 표시되며, 서로 같은 표시를 가진 두 동굴은 없다. 산 지형의 경계에 있는 모든 칸은 지나갈 수 없다. 1 ≤ T ≤ 20.

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

3 ≤ R, C ≤ 10.

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

3 ≤ R, C ≤ 60.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 산 지형의 행 수와 열 수를 나타내는 정수 R과 C가 담긴 줄로 시작한다.

그다음에는 산 지형을 나타내는 R개의 줄이 주어지며, 각 줄에는 C개의 문자가 있다. 위 예시와 마찬가지로 '#' 문자는 지나갈 수 없는 칸을, '.' 문자는 지나갈 수 있는 칸을, 숫자 '0'-'9'는 동굴을 나타낸다. 동굴 역시 지나갈 수 있는 칸이다.

각 테스트 케이스마다 먼저 "Case #x:"이 담긴 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이다. 0부터 시작해 오름차순으로 각 동굴 C에 대해 "C: $n_{C}$ $L_{C}$" 한 줄을 출력한다. 여기서 C는 동굴 번호이고, $n_{C}$는 해당 동굴에 도달할 수 있는 출발 칸의 수이며, $L_{C}$는 위에서 정의한 문자열 "Lucky" 또는 문자열 "Unlucky"이다.

첫 번째 테스트 케이스에서 행운의 동굴에 사용할 수 있는 유효한 계획의 예시는 다음과 같다.

• 동굴 0에는 빈 계획을 사용할 수 있다. 그 동굴에 도달할 수 있다면 이미 올바른 위치에 있는 것이다!

• 동굴 1에는 오른쪽-아래쪽-왼쪽 계획을 사용할 수 있다.

• 동굴 3에는 오른쪽-오른쪽-왼쪽-아래쪽-아래쪽-아래쪽-왼쪽 계획을 사용할 수 있다.