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:
/*http://agc014.contest.atcoder.jp/submissions/1266693*/
import java.util.ArrayDeque;
import java.util.Scanner;
import java.util.function.LongSupplier;
import java.util.stream.IntStream;
 
public class Main{
	static final Scanner s=new Scanner(System.in);
	static final long[] fal_rnd(long[] ar,LongSupplier sp){
		int l=-1,r=ar.length;
		while(l+1!=r)
			ar[Math.random()<0.5?++l:--r]=sp.getAsLong();
		return ar;
	}
	static final IntStream REPS(int v){
		return IntStream.range(0,v);
	};
	static int h,w,k;
	public static void main(String[] __){
		h=s.nextInt();
		w=s.nextInt();
		k=s.nextInt();
		char[][]f=new char[h][];
		int x=-1,y=-1;
		for(int i=0;i<h;i++) {
			String in=s.next();
			if(x==-1) {
				x=in.indexOf('S');
				y=i;
			}
			f[i]=in.toCharArray();
		}
		
		int u=y,d=y,r=x,l=x;
		
		int[]dx= {0,1,0,-1};
		int[]dy= {1,0,-1,0};
		
		
		ArrayDeque<Point> deque=new ArrayDeque<>();
		deque.add(new Point(y,x));
		for(int i=0;i<=k;i++) {
			for(int j=deque.size();j>0;j--) {
				Point poll=deque.poll();
				
				u=Math.min(u,poll.y);
				d=Math.max(d,poll.y);
				l=Math.min(l,poll.x);
				r=Math.max(r,poll.x);
				
				
				f[poll.y][poll.x]='#';
				for(int bufd=0;bufd<4;bufd++) {
					if(range(poll.y+dy[bufd],poll.x+dx[bufd])
							&&f[poll.y+dy[bufd]][poll.x+dx[bufd]]=='.') {
						deque.add(new Point(poll.y+dy[bufd],poll.x+dx[bufd]));
				f[poll.y+dy[bufd]][poll.x+dx[bufd]]='#';
					}
				}
			}
		}
		/*
		System.out.println(u);
		System.out.println(h-1-d);
		System.out.println(l);
		System.out.println(w-1-r);
		*/
		System.out.println((IntStream.of(u,h-1-d,l,w-1-r).min().getAsInt()+k-1)/k+1);
	}
	
	static final boolean range(int y,int x) {
		return 0<=y&&y<h&&0<=x&&x<w;
	}
	static class Point{
		int y,x;
		Point(int y,int x){
			this.y=y;
			this.x=x;
		}
	}
}