Descending in the Dark (Large)

You are on the face of Mount Everest. You have to find shelter before you freeze, and it is dark.

The good news is that you already memorized the layout of the mountain. It is a grid. Some squares are impassable, and some squares hold caves where you can rest for the night. The bad news is that you do not know where you are, and the face is too steep to climb, so you can only move one square left, right, or down.

Here is an example layout. A . is a passable square, a # is an impassable square, and a digit is a cave.

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

Because it is dark, you move by following a plan, a list of instructions that each tell you to move one square left, right, or down. If an instruction would take you to a passable square or to a cave, you follow it. If it would take you to an impassable square, you ignore it. Either way you go on to the next instruction, until the whole plan is done.

To plan your descent, you want to know two things about every cave $C$.

• Which squares is it possible to reach $C$ from? Call that set of squares $S_C$, and its size $n_C$.
• Is there a single plan that finishes at cave $C$ when you follow it from any square in $S_C$? If there is, the cave is lucky.

You might pass several caves while following a plan. Only the square you stand on after the last instruction matters, not the caves you visit on the way.

In the layout above, cave 0 is lucky. There are 9 squares it can be reached from, counting the cave itself, and the plan left, left, down, down, left, down finishes at the cave from every one of them.

The first line has the number of test cases, $T$. Each test case begins with a line holding the number of rows $R$ and the number of columns $C$ of the mountain layout.

$R$ lines follow, each holding $C$ characters that describe the layout. As in the example above, a # is an impassable square, a . is a passable square, and the digits 0 to 9 are caves. A cave is passable as well.

For each test case, print one line Case #x:, where $x$ is the test case number starting from 1.

Then, for each cave $C$ in increasing order of cave number starting from 0, print one line C: nC LC. Here $C$ is the cave number, $n_C$ is the number of squares you can reach the cave from, and $L_C$ is Lucky if the cave is lucky and Unlucky otherwise.

• Each layout has between 1 and 10 caves.
• If a layout has $d$ caves, they are labeled with the digits $0, 1, \dots, d-1$, and no two caves carry the same digit.
• Every square on the boundary of the layout is impassable.
• $1 \le T \le 20$
• $3 \le R, C \le 60$

Here are plans that work for the lucky caves of the first example.

• Cave 0 works with the empty plan. If you can reach the cave at all, you already stand on it.
• Cave 1 works with the plan right, down, left.
• Cave 3 works with the plan right, right, left, down, down, down, left.