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.io.*;
import java.util.*;

public class Main implements Runnable {

    private void solve() throws IOException {

        int R = nextInt();
        int C = nextInt();
        int K = nextInt();

        String[] s = new String[R];
        for(int i = 0; i < R; ++i) {
            s[i] = reader.readLine();
        }
        Queue<Integer> q = new LinkedList<>();
        int[][] dist = new int[R][C];
        for(int[] ini : dist) Arrays.fill(ini,1 << 30);
        int meR = -1;
        int meC = -1;
        for(int i = 0; i < R; ++i) {
            for(int j = 0; j < C; ++j) {
                if(s[i].charAt(j) == 'S') {
                    meR = i;
                    meC = j;
                }
            }
        }
        dist[meR][meC] = 0;
        q.offer(meR);
        q.offer(meC);

        Queue<Integer> special = new LinkedList<>();

        int best = Integer.MAX_VALUE;
        int[] dx = new int[] { 1,-1,0,0 };
        int[] dy = new int[] { 0,0,1,-1 };

        while(!q.isEmpty()) {

            boolean move = false;
            int r = q.poll();
            int c = q.poll();
            if(r == 0 || c == 0 || r == R - 1 || c == C - 1) {
                writer.println(1);
                return;
            }
            for(int a = 0; a < 4; ++a){
                int x = dx[a] + r;
                int y = dy[a] + c;
                if(x >=0 && x < R && y >=0 && y < C && s[x].charAt(y) == '.') {
                    if(dist[x][y] > dist[r][c] + 1 && ((dist[r][c] + 1 <= K))) {
                        dist[x][y] = dist[r][c] + 1;
                        q.offer(x);
                        q.offer(y);
                        move = true;
                    }
                }
            }
            if(!move) {
                special.offer(r);
                special.offer(c);
            }

        }
        while(!special.isEmpty()) {
            int r = special.poll();
            int c = special.poll();
            int curMin = Math.min(r,c);
            curMin = Math.min(curMin,Math.min(R-r-1,C-c-1));

            int need = curMin / K;
            if(curMin % K != 0) ++need;
            best = Math.min(best, need + 1);

        }
        writer.println(best);
    }


    public static void main(String[] args) {
        new Main().run();
    }



    BufferedReader reader;
    //    BufferedReader reader2;
    StringTokenizer tokenizer;
    PrintWriter writer;
    //    BufferedWriter writer;

    public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
//            reader = new BufferedReader(new FileReader("input.txt"));
            //            reader2 = new BufferedReader(new FileReader("1.in"));
            tokenizer = null;
            writer = new PrintWriter(System.out);
//            writer = new     PrintWriter("output.txt");
//                                                    writer = new BufferedWriter(System.out);
            //                        writer = new BufferedWriter(new OutputStreamWriter(System.out));
            solve();
            reader.close();
            //            reader2.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    short nextShort() throws IOException {
        return Short.parseShort(nextToken());
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }

        return tokenizer.nextToken();
    }

}