### 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 Ai,j. If Ai,j= '`#`', the room is locked and cannot be entered; if Ai,j= '`.`', the room is not locked and can be freely entered. Takahashi is currently at the room where Ai,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 Ai,j is '`#`' , '`.`' or '`S`'.
• There uniquely exists (i,j) such that Ai,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
A1,1A1,2...A1,W
:
AH,1AH,2...AH,W
```

### Output

Print the minimum necessary number of casts.

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

### Sample Output 1

```1
```

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

```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.

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

```2
```

### Submitting .cpp to 'closedrooms'

Time Limit: 1 Seconds
Memory Limit: 256MB