### ** closedrooms**

### 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`_{i,j} is '`#`

' , '`.`

' 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:

`H` `W` `K`
`A`_{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