Descending in the Dark (Small)

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. The layout is a grid. Some squares are impassable, and some squares hold a cave where you can rest for the night. The bad news is that you do not know which square you are standing on, and the slope is too steep to climb up. You can only move one square left, right, or down.

The layout is written like this. A '.' is a passable square, a '#' is an impassable square, and a digit is a cave. A square with a cave is passable as well.

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

Since you cannot see anything, you move by following a plan you fix in advance. A plan is a list of instructions, and each instruction tells you to move one square left, right, or down. If the square the instruction points at is passable, you move onto it. If it is impassable, you ignore that instruction and stay where you are. Either way you go on to the next instruction, and you keep going until the last instruction of the plan.

For the descent you want to know two things about each cave $k$.

• Which squares can you reach cave $k$ from? Call that set of squares $S_k$ and its size $n_k$.
• Is there a single plan that finishes with you at cave $k$ no matter which square of $S_k$ you start from? If there is, cave $k$ is lucky.

You may pass other caves while you follow a plan. Only the square you stand on after the last instruction counts, and the caves you passed on the way do not matter.

In the layout above, cave 0 is lucky. There are 9 squares you can reach cave 0 from, counting cave 0 itself, and the plan left, left, down, down, left, down finishes at cave 0 from every one of those 9 squares.

The first line has the number of test cases $T$.

The first line of each test case has the number of rows $R$ and the number of columns $C$ of the layout. Each of the next $R$ lines has $C$ characters describing the layout. A '#' is an impassable square, a '.' is a passable square, and the digits '0' to '9' are caves.

There are between 1 and 10 caves. If there are $d$ caves, they are numbered $0, 1, \dots, d-1$, and no two caves have the same number. Every square on the boundary of the layout is impassable.

$1 \le T \le 20$

$3 \le R, C \le 10$

For each test case, first print Case #x: on a line of its own, where $x$ is the test case number starting from 1.

Then, in increasing order of cave number, print one line per cave $k$ holding the cave number $k$, a colon, a space, $n_k$, a space, and $L_k$. Here $n_k$ is the number of squares you can reach cave $k$ from, and $L_k$ is Lucky if cave $k$ is lucky and Unlucky otherwise.

For the first layout of the sample input, these plans work for the lucky caves.

• Cave 0: the empty plan. Cave 0 is the only square you can reach cave 0 from, so you do not have to move at all.
• Cave 1: right, down, left.
• Cave 3: right, right, left, down, down, down, left.