A Digging Problem

The cave is on fire and smoke is everywhere. You want to dig your way down to the bottom row of the cave, where you can breathe. The trouble is that the cave has air holes inside it, and one long fall hurts you.

The cave is an $R \times C$ grid. Every cell is either an air hole or solid rock. You start at $(1, 1)$, the top-left cell. The coordinate $(i, j)$ means row $i$ from the top and column $j$ from the left.

Moving works like this. You move one cell at a time, left or right, and the cell you move into has to be an air hole. After the move, if the cell directly below you is an air hole, you fall down until you hit solid rock or reach the bottom row of the cave. One fall covers at most $F$ cells, and a longer fall hurts you. You cannot move left or right while falling.

Digging works like this. You can turn a cell of solid rock into an air hole. Only two cells can be dug: the one diagonally down and to your right, and the one diagonally down and to your left. The cell directly above the cell you dig has to be an air hole. You cannot dig while falling. A cell you have dug stays an air hole.

Your goal is to reach the bottom row of the cave without getting hurt while digging as few cells as possible.

Here is how the operations work in the cave shown below.

You start at $(1, 1)$ and move right three times to $(1, 4)$. You dig the rock at $(2, 5)$, so cell A in the figure becomes an air hole. You move one cell right, and since the cell directly below is empty you fall three cells to $(4, 5)$. Now you dig the rock at $(5, 6)$, so cell B in the figure becomes an air hole. You move one cell right again, and since the cell directly below is empty you fall one cell to $(5, 6)$. You have reached the bottom row of the cave by digging 2 cells.

The first line of input gives the number of test cases, $N$. $N$ test cases follow. The first line of each test case has the format

R C F

where $R$ is the number of rows in the cave, $C$ is the number of cells in each row, and $F$ is the largest distance you can fall without getting hurt. Then come $R$ lines of $C$ characters each. Each character is one of two things:

• # for solid rock
• . for an air hole

The top-left cell is always an air hole, and the cell directly below it is always solid rock.

Limits

• $1 \le N \le 50$
• $2 \le R \le 10$
• $2 \le C \le 8$
• $1 \le F < R$

For each test case, output one line. If you cannot reach the bottom row of the cave, use the format

Case #X: No

If you can reach it, also output the minimum number of cells $D$ that need digging.

Case #X: Yes D

Here $X$ is the test case number, starting from 1.