A Digging Problem (Large)

A fire has broken out in the cave and smoke is everywhere. You want to dig your way down to the bottom of the cave, where you can breathe. The trouble is that the cave contains air holes, and falling too far hurts you.

The cave is an $R \times C$ grid. Every cell is either solid rock or an air hole. You start on the top left cell $(1, 1)$. Here $(r, c)$ is the cell in row $r$ from the top and column $c$ from the left.

You can move one cell at a time, left or right, and only if the destination cell is an air hole. After you move, if the cell below you is an air hole, you fall until you hit solid rock or reach the bottom of the cave. Falling more than $F$ cells hurts you, so every single fall covers at most $F$ cells. While falling you cannot move left or right.

You can also dig, which turns a cell of solid rock into an air hole. Standing on $(r, c)$, the only cells you can dig are $(r+1, c+1)$, down and to the right, and $(r+1, c-1)$, down and to the left. The cell directly above the one you dig, so $(r, c+1)$ or $(r, c-1)$, has to be an air hole. While falling you cannot dig. You can dig several cells without leaving your position, and a cell you dug stays an air hole for the rest of the descent.

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

The cave below has $R = 5$, $C = 8$ and $F = 3$.

1. Start at $(1, 1)$ and move right three times to $(1, 4)$.
2. Dig the rock at $(2, 5)$. Cell A in the picture becomes an air hole.
3. Move right one cell. Nothing is below you, so you fall three cells and land on $(4, 5)$.
4. Dig the rock at $(5, 6)$. Cell B in the picture becomes an air hole.
5. Move right one cell. Nothing is below you, so you fall one cell and land on $(5, 6)$.

You reached the bottom of the cave by digging 2 cells.

The first line holds the number of test cases, $N$. $N$ test cases follow.

The first line of each test case holds three integers.

R C F

$R$ is the number of rows in the cave, $C$ is the number of columns, and $F$ is the largest distance you can fall without getting hurt. The next $R$ lines hold $C$ characters each, with no spaces. 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 below it is always solid rock.

Limits

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

For each test case, print one line in the format

Case #X: No

or

Case #X: Yes D

where $X$ is the case number, starting from 1. Print No if you cannot reach the bottom of the cave. If the bottom can be reached, print Yes, a space, and $D$, the minimum number of cells that need digging.