동굴 파기

동굴에 불이 나서 온통 연기다. 숨을 쉴 수 있는 동굴 맨 아래 줄까지 파고 내려가려 한다. 문제는 동굴 안에 빈 구멍이 있어서 한 번에 너무 많이 떨어지면 다친다는 점이다.

동굴은 $R \times C$ 격자로 주어진다. 각 칸은 빈 구멍이거나 단단한 암석이다. 출발 위치는 왼쪽 위 칸인 $(1, 1)$이다. 좌표 $(i, j)$는 위에서 $i$번째 줄, 왼쪽에서 $j$번째 칸을 뜻한다.

이동 규칙은 이렇다. 한 번에 한 칸씩 왼쪽이나 오른쪽으로 옮길 수 있고, 옮겨 갈 칸이 빈 구멍이어야 한다. 옮긴 뒤 바로 아래 칸이 빈 구멍이면 암석에 닿거나 동굴 맨 아래 줄에 이를 때까지 아래로 떨어진다. 한 번에 떨어지는 거리는 $F$ 이하여야 하고, 그보다 길게 떨어지면 다친다. 떨어지는 동안에는 좌우로 움직일 수 없다.

파는 규칙은 이렇다. 암석 칸을 빈 구멍으로 바꿀 수 있다. 팔 수 있는 칸은 두 개뿐인데, 오른쪽 아래 대각선 칸과 왼쪽 아래 대각선 칸이다. 파려는 칸의 바로 위 칸은 빈 구멍이어야 한다. 떨어지는 동안에는 팔 수 없다. 한 번 판 칸은 그대로 빈 구멍으로 남는다.

목표는 다치지 않고 동굴 맨 아래 줄에 도달하면서 파는 칸 수를 최소로 만드는 것이다.

그림에 있는 동굴에서 어떻게 움직이는지 따라가 보자.

$(1, 1)$에서 출발해 오른쪽으로 세 번 움직여 $(1, 4)$로 간다. $(2, 5)$의 암석을 파면 그림의 A 칸이 빈 구멍이 된다. 오른쪽으로 한 칸 움직이면 바로 아래가 비어 있으므로 세 칸 떨어져 $(4, 5)$에 닿는다. 이제 $(5, 6)$의 암석을 파면 그림의 B 칸이 빈 구멍이 된다. 다시 오른쪽으로 한 칸 움직이면 바로 아래가 비어 있으므로 한 칸 떨어져 $(5, 6)$에 닿는다. 두 칸을 파서 동굴 맨 아래 줄에 도달했다.

첫 줄에 테스트 케이스의 개수 $N$이 주어진다. 이어서 $N$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄은 다음 형식이다.

R C F

$R$은 동굴의 줄 수, $C$는 각 줄의 칸 수, $F$는 다치지 않고 떨어질 수 있는 최대 거리다. 다음 $R$개의 줄에는 각각 $C$개의 문자가 주어지고, 각 문자는 둘 중 하나다.

• # 은 단단한 암석
• . 은 빈 구멍

왼쪽 위 칸은 항상 빈 구멍이고, 그 바로 아래 칸은 항상 암석이다.

제한

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

각 테스트 케이스마다 한 줄씩 출력한다. 동굴 맨 아래 줄에 도달할 수 없으면 다음 형식으로 출력한다.

Case #X: No

도달할 수 있으면 파야 하는 칸 수의 최솟값 $D$를 함께 출력한다.

Case #X: Yes D

$X$는 1부터 시작하는 테스트 케이스 번호다.