Farewell, My Friend

Time Limit: 10 Seconds    Memory Limit: 32768 KB

Liz and Lilly used to be very good friends, but recently, they got into a silly quarrel and finally decided to say farewell to each other. 'I don't want to see you any more! I must put some new rocks somewhere so that no matter how I travel from my house, I can never see your face.' They both said.

They live in a small village which is divided into n*n grid. Liz always lives in the top-left corner (i.e grid (1,1)), and Lilly always lives in the bottom-right corner. (i.e gird(n,n)). Each grid of land is one of the following types: land, lake or rock. They cannot move across a rock or a lake, of course. And although people cannot see through a rock, it's easy for them to see through a piece of land or a lake. Note that they can only move north, south, east or west one grid at a time, NOT diagonally, and they are a bit shortsighted - they can only see things that are no more than k grids away in front of them (in the same row or column, they don't see anyhing diagonally).

Since they're both lazy, they want to put as few new rocks as possible. A new rock can only be put on a piece of land that at least one of the two girls can reach from her house. Note that they don't want to put new rocks too close to their houses, so the new rocks must be at least m grids away from both of the houses. By definition, grid(x1,y1) and grid(x2,y2) are supposed to be abs(x1-x2)+abs(y1-y2) grids away from each other.

Input

The input will contain no more than 8 test cases. Each test case begins with a line containing three integers n, k and m(5<=n<=20, 1<=k<=n, 1<=m<=n) separated by a single space. The following n lines each contains n characters indicating the map of a village. The capital letter 'O' represents a lake, '*' represents a rock, '.' represents a piece of land. The test case containing n=0, k=0, m=0 will terminate the input, you should not give an answer to this 'test case'. No extra spaces at the beginning/end of each line.

Output

Output the least number of new rocks that must be put in order to separate them. Print your answer in a single line for each test case. If no solution found, you should output -1 in the corresponding line.

Sample Input

7 4 4
.......
......*
....*O.
**.*.O.
...*...
.OO..*.
.......
0 0 0

Sample Output

2

Submit

Source: OIBH Online Programming Contest #1