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:
typedef long long ll;
typedef long double ld;
#include <bits/stdc++.h>
using namespace std;

int main() {
    ll h,w,k;
    std::cin >> h>>w>>k;
    
    vector<string> a(h);
    pair<ll,ll> s;
    for (int i = 0; i < h; i++) {
        std::cin >> a[i];
        for (int j = 0; j < w; j++) {
            if(a[i][j]=='S')s = {i,j};
        }
    }
    
    set<pair<ll,ll>> se;
    
    queue<tuple<ll,ll,ll>> q;
    q.push({s.first,s.second,k});
    se.insert({s.first,s.second});
    while(q.size()){
        auto [xx,yy,rem] = q.front();q.pop();
        if(rem==0)continue;
        for (int x = -1, y = 0, iii = 0; iii < 4; x += y, y = x - y, x = y - x, ++iii) {
            if(xx+x<0||xx+x>h-1||yy+y<0||yy+y>w-1)continue;
            if(a[xx+x][yy+y]=='.'){
                if(se.find({xx+x,yy+y})!=se.end())continue;
                if(rem-1>0)q.push({xx+x,yy+y,rem-1});
                se.insert({xx+x,yy+y});
            }
        }
    }
    ll ans = 1e15;
    for (auto e : se) {
        auto minx = min(e.first,h-1-e.first);
        auto miny = min(e.second,w-1-e.second);
        ans = min(ans, (min(minx,miny)+k-1)/k);
    }
    std::cout << 1+ans << std::endl;
}