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 JAVA):

Solution:
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		new Main().solve();
	}
	int H,W,K;
	String[]A;
	void solve(){
		Scanner sc=new Scanner(System.in);
		int count=1;
		H=sc.nextInt();
		W=sc.nextInt();
		K=sc.nextInt(); //=魔法の移動回数=開けられる部屋の個数
		A=new String[H];
		for(int i=0;i<H;i++){
			A[i]=sc.next();
		}
		int fx=-1;
		int fy=-1;
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				if(A[i].charAt(j)=='S'){
					fx=j;
					fy=i;
				}
			}
		}
		Queue<Integer> nowq=new LinkedList<Integer>();
		nowq.add(encode(fy,fx));
		
		int[] vy=new int[]{1,0,-1,0};
		int[] vx=new int[]{0,1,0,-1};
		
		boolean[][] check=new boolean[H][W];
		
		//最初のKで到達できるところ
			Queue<Integer> endq=new LinkedList<Integer>();
			
			for(int i=0;i<K;i++){
				Queue<Integer> nextq=new LinkedList<Integer>();
				while(!nowq.isEmpty()){
					int now=nowq.poll();
					int y=now/1000;
					int x=now%1000;
					for(int j=0;j<4;j++){
						int ny=y+vy[j];
						int nx=x+vx[j];
					
						if(!ok(ny,nx))continue;
					
						if(check[ny][nx])continue;
					
						if(A[ny].charAt(nx)=='.' && (ny==0 || ny==H-1 || nx==0 || nx==W-1)){
							System.out.println(count);
							return;
						}
						else if(A[ny].charAt(nx)=='#' && !check[y][x]){
							endq.add(encode(y,x));
							check[y][x]=true;
						}
						else if(A[ny].charAt(nx)=='.'){
							nextq.add(encode(ny,nx));
							check[ny][nx]=true;
							endq.add(encode(ny,nx));
						}
					}
				}
				nowq=nextq;
			}
			int n=endq.size();
			
			int Min=999999999;
			for(int i=0;i<n;i++){
				int now=endq.poll();
				int y=now/1000;
				int x=now%1000;
				y=Math.min(y, H-1-y);
				x=Math.min(x, W-1-x);
				if(Min>Math.min(x, y))Min=Math.min(x, y);
			}
			if(Min%K==0)System.out.println(Min/K+1);
			else System.out.println(Min/K+2);
	}
	int encode(int y,int x){
		return y*1000+x;
	}
	boolean ok(int y,int x){
		return y>=0 && x>=0 && y<H && x<W;
	}
}