#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### Closed Rooms

### Problem Statement

Takahashi is locked within a building.

This building consists of `H×W` rooms, arranged in `H` rows and `W` columns.
We will denote the room at the `i`-th row and `j`-th column as `(i,j)`. The state of this room is represented by a character `A _{i,j}`. If

`A`'

_{i,j}=`#`

', the room is locked and cannot be entered; if `A`'

_{i,j}=`.`

', the room is not locked and can be freely entered.
Takahashi is currently at the room where `A`'

_{i,j}=`S`

', which can also be freely entered.Each room in the `1`-st row, `1`-st column, `H`-th row or `W`-th column, has an exit.
Each of the other rooms `(i,j)` is connected to four rooms: `(i-1,j)`, `(i+1,j)`, `(i,j-1)` and `(i,j+1)`.

Takahashi will use his magic to get out of the building. In one cast, he can do the following:

- Move to an adjacent room at most
`K`times, possibly zero. Here, locked rooms cannot be entered. - Then, select and unlock at most
`K`locked rooms, possibly zero. Those rooms will remain unlocked from then on.

His objective is to reach a room with an exit. Find the minimum necessary number of casts to do so.

It is guaranteed that Takahashi is initially at a room without an exit.

### Constraints

`3 ≤ H ≤ 800``3 ≤ W ≤ 800``1 ≤ K ≤ H×W`- Each
`A`is '_{i,j}`#`

' , '`.`

' or '`S`

'. - There uniquely exists
`(i,j)`such that`A`'_{i,j}=`S`

', and it satisfies`2 ≤ i ≤ H-1`and`2 ≤ j ≤ W-1`.

### Input

Input is given from Standard Input in the following format:

HWKA..._{1,1}A_{1,2}A:_{1,W}A..._{H,1}A_{H,2}A_{H,W}

### Output

Print the minimum necessary number of casts.

### Sample Input 1

3 3 3 #.# #S. ###

### Sample Output 1

1

Takahashi can move to room `(1,2)` in one cast.

### Sample Input 2

3 3 3 ### #S# ###

### Sample Output 2

2

Takahashi cannot move in the first cast, but can unlock room `(1,2)`.
Then, he can move to room `(1,2)` in the next cast, achieving the objective in two casts.

### Sample Input 3

7 7 2 ####### ####### ##...## ###S### ##.#.## ###.### #######

### Sample Output 3

2

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 40 | 1s | 256MB | Minimum |

2 | 0 | 3 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o closedrooms -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512