Success

The road to success is never smooth. Obstacles fill it, and you can get stuck and stop right where you are. So you want to blow them up.

The road to success lies on an $N \times M$ grid. To succeed, start at the top-left cell, step only onto cells without obstacles that are adjacent up, down, left, or right, and reach the bottom-right cell. One blast operation can remove every obstacle inside a $D \times D$ subgrid. Blasting takes a lot of effort, so find the minimum number of blasts needed to succeed.

The first line contains the number of rows $N$, the number of columns $M$, and the blast range $D$ ($D \le N$, $M \le 500$, $1 \le D \le 100$). Next, $N$ lines follow, each a string of length $M$ describing one row of the grid. "." is a cell without an obstacle, and "#" is a cell with an obstacle. The start and the goal cells have no obstacles.

Print the minimum number of blast operations on the first line.