描述

给定一个 \(H \times W\) 的矩阵，有 \(H\) 行 \(W\) 列，矩阵中只有三种字符，第 \(i\) 行第 \(j\) 列的字符\(A[i][j]=\) '#'，表示此方格不可通行，若\(A[i][j]=\) '.'，表示此方格可以通行，若\(A[i][j]=\) 'S'，表示 \(\text{Smart}\) 的起始位置。\(\text{Smart}\) 想要走出矩阵，即他要到达第 \(1\) 行或第 \(H\) 行或第 \(1\) 列或第 \(W\) 列。\(\text{Smart}\) 会一种魔法，使用这种魔法一次能做如下两件事（先后顺序不能颠倒）：
1. 最多 \(K\) 次移动，每次移动到相邻(上、下、左、右)的可通行的方格，也可以一次都不移动；
2. 选择最多 \(K\) 个不可通行的方格，将它们全变成永久可通行的方格，也可以一个方格都不选择。
你的任务是求 \(\text{Smart}\) 至少需要使用多少次魔法，才能走出矩阵，即到达第 \(1\) 行或第 \(H\) 行或第 \(1\) 列或第 \(W\) 列。

格式

输入格式

第一行三个整数\(H,W,K\)。
接下来 \(H\) 行，每行 \(W\) 个字符描述矩阵。

输出格式

输出一行包含一个整数，表示 \(\text{Smart}\) 至少使用魔法的次数。

样例1

样例输入1

3 3 3
#.#
#S.
###

样例输出1

1

限制

\(100\%\)的数据：\(3 ≤ H ≤ 1000，3 ≤ W ≤ 1000，1≤ K ≤ H×W\)。
数据保证矩阵中只有一个'S'，且不在矩阵的第 \(1\) 行或第 \(H\) 行或第 \(1\) 列或第 \(W\) 列。