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

Solution (in CPP):

Solution:
#include <cstdio>
#include <algorithm>
using namespace std;

int R, C, K, Sr, Sc;
bool m[805][805];
int dist[805][805];

int minr = 1e9, maxr, minc = 1e9, maxc;

bool seen[805][805];
int sr[10000000], sc[10000000], ss, se;

void push(int r, int c, int d) {
    if (seen[r][c] || !m[r][c]) return;
    seen[r][c] = 1;
    sr[se] = r;
    sc[se++] = c;
    dist[r][c] = d;
}

int main() {
    scanf("%d %d %d", &R, &C, &K);
    char s;
    for (int r = 1; r <= R; r++) for (int c = 1; c <= C; c++) {
        scanf(" %c", &s);
        m[r][c] = 1;
        if (s == '#') m[r][c] = 0;
        else if (s == 'S') Sr = r, Sc = c;
    }
    sr[se] = Sr, sc[se++] = Sc;
    seen[Sr][Sc] = 1;
    while (ss < se) {
        int r = sr[ss], c = sc[ss];
        ss++;
        if (r < minr) minr = r;
        if (r > maxr) maxr = r;
        if (c < minc) minc = c;
        if (c > maxc) maxc = c;
        if (dist[r][c] < K) {
            push(r+1,c,dist[r][c]+1);
            push(r-1,c,dist[r][c]+1);
            push(r,c+1,dist[r][c]+1);
            push(r,c-1,dist[r][c]+1);
        }
    }

    int d = min(min(minr-1,minc-1),min(R-maxr,C-maxc));
    printf("%d\n", 1 + (d+K-1)/K);
}