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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

int A[808][808];
int dr[4]={-1,1,0,0};
int dc[4]={0,0,1,-1};
const int INF=1e9;

int main(){
  rep(i,808) rep(j,808) A[i][j]=INF;
  int H,W,K; cin>>H>>W>>K;
  string S[H];
  int sr,sc;
  rep(i,H){
    cin>>S[i];
    rep(j,W) if(S[i][j]=='S'){
      sr=i;
      sc=j;
    }
  }
  A[sr][sc]=0;
  queue<pair<int,int> > que;
  que.push({sr,sc});
  while(que.size()){
    pair<int,int> P=que.front(); que.pop();
    int r=P.first, c=P.second;
    rep(i,4){
      int rr=r+dr[i], cc=c+dc[i];
      if(rr>=H||rr<0||cc>=W||cc<0) continue;
      if(S[rr][cc]!='.'||A[rr][cc]!=INF) continue;
      A[rr][cc]=A[r][c]+1;
      que.push({rr,cc});
    }
  }

  int ans=1e9;
  rep(i,H) rep(j,W) if(A[i][j]<=K){
    int x=i/K+(i%K==0?0:1);
    int y=(H-1-i)/K+((H-1-i)%K==0?0:1);
    int z=j/K+(j%K==0?0:1);
    int w=(W-1-j)/K+((W-1-j)%K==0?0:1);
    ans=min({ans,x,y,z,w});
  }
  cout<<ans+1<<endl;
  return 0;
}