小$J$被关在密室里！

密室的构造是一个$H×W$的棋盘，即有$H$行$W$列，第$i$行第$j$列的房间用$A_{i,j}$ 表示。

• 若 $A_{i,j}$=#， 则该房间的门是锁上的；
• 若 $A_{i,j}$ =.， 则该房间是可以自由进出的；
• 小$J$被困在 $A_{i,j}$ =S 的地方，该房间是可以自由进出的。

房间是四相邻的，即($i,j$)可以移动到$(i+1,j),(i-1,j),(i,j-1),(i,j+1)$

小$J$将通过如下方式逃脱密室，每一回合，她会按顺序执行如下操作：

• 移动至多$K$ 次，可以不移动，此时被锁着的房间是不能够进入的
• 选择至多$K$ 个锁着的房间打开，可以不选择任何房间，从此那些房间将一直可以自由进出

出口在密室的四周，即第$1$行，第$1$列，第$H$行，第$W$列的所有房间，出口一开始可能是被锁住的。

你需要用最少的回合移动到出口，输出这个回合数。

输入格式

第一行读入三个整数$H,W,K$

接下来$H$行，每行$W$个字符，表示$A_{i,j}$

输出格式

输出一行一个数，表示小$J$最少要用多少回合逃出密室。

样例

样例输入1

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

样例输出1

1

• 样例解释：小$J$可以在一个回合内移动到（$1，2$）

样例输入2

3 3 3
###
#S#
###

样例输出2

2

• 样例解释：小$J$第一个回合不能移动，但她解锁了房间（$1，2$），然后她在第二个回合移动到（$1，2$）逃离密室。

样例输入3

7 7 2
#######
#######
##...##
###S###
##.#.##
###.###
#######

样例输出3

2

数据范围与提示

• $3 \leq H ,W \leq 800$
• $1 \leq K \leq H \times W$
• $A_{i,j}$ 是 # ,. ,S 中的一种，有且仅有一个$A_{i,j}$为S
• $Subtask1（30分）$：$H,W \leq 4$
• $Subtask2（10分）$：不存在$A_{i,j}$ =#
• $Subtask3（10分）$：不存在$A_{i,j}$=.
• $Subtask4（50分）$：无特殊限制

• 时间限制：$2000\mathrm{ms}$
• 空间限制：$524288\mathrm{KB}$