p03725 AtCoder Grand Contest 014 - Closed Rooms
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.

Examples

Input

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


Output

1


Input

3 3 3
.#
S.


Output

1


Input

3 3 3

S#


Output

2


Input

7 7 2


...##
S###
.#.##
.###


Output

2
```python
from collections import deque
h,w,k = map(int,input().split())
a = []
for i in range(h):
  b = input()
  tmp = []
  for j in range(w):
    tmp.append(b[j])
    if b[j] == "S":
      sx = i
      sy = j
  a.append(tmp)
ma = [[0]*w for i in range(h)]
def dfs(x,y,z):
  if ma[x][y] == 1:
    return
  if z>k:
    return
  ma[x][y] = 1
  if x > 0 and a[x-1][y]== ".":
    que.append([x-1,y,z+1])
  if y > 0 and a[x][y-1]== ".":
    que.append([x,y-1,z+1])
  if x <h-1 and a[x+1][y]==".":
    que.append([x+1,y,z+1])
  if y <w-1 and a[x][y+1]==".":
    que.append([x,y+1,z+1])
que = deque([[sx,sy,0]])
while que:
  x,y,z = que.popleft()
  dfs(x,y,z)
ans = float("inf")
for i in range(h):
  for j in range(w):
    if ma[i][j] == 1:
      ans = min(ans,1+(h-i-1)//k+ (1 if (h-i-1)%k else 0),1+(w-j-1)//k+ (1 if (w-j-1)%k else 0),
               1+(i)//k+ (1 if (i)%k else 0),1+(j)//k+ (1 if (j)%k else 0))
print(ans)
```