성공

성공으로 가는 길은 평탄하지 않다. 길에는 온갖 장애물이 가득하고, 장애물에 막히면 그 자리에 주저앉을 수도 있다. 그래서 장애물을 폭파하려고 한다.

성공으로 가는 길은 $N \times M$ 격자 위에 놓여 있다. 성공하려면 맨 왼쪽 위 칸에서 출발해 장애물이 없는 상하좌우 인접 칸을 밟으며 맨 오른쪽 아래 칸에 도착해야 한다. 폭파 작업 한 번으로 $D \times D$ 격자 안에 있는 모든 장애물을 없앨 수 있다. 다만 폭파 작업에는 큰 힘이 들기 때문에, 성공하려면 최소 몇 번의 폭파 작업이 필요한지 알고 싶다.

첫 번째 줄에 격자의 행의 개수 $N$, 열의 개수 $M$, 폭파의 범위 $D$가 주어진다 ($D \le N$, $M \le 500$, $1 \le D \le 100$). 그 다음 $N$개의 줄에 격자의 각 행을 나타내는 길이 $M$의 문자열이 주어진다. "."은 장애물이 없는 칸, "#"은 장애물이 있는 칸이다. 출발 지점과 성공 지점에는 장애물이 없다.

첫 번째 줄에 폭파 작업의 최소 횟수를 출력한다.