咲夜需要穿过一片弹幕区，由于咲夜发动了符卡“The World”,所以弹幕是静止的。这片弹幕区以一个n*m的矩阵的形式给出。

‘.’表示这个位置是安全的，’x’表示这个位置上是有子弹的，禁止通行。咲夜每次能向左、右、下三个方向的相邻格子走，但是不能向上走。 同时由于时间有限，咲夜在进入每一行之后最多只能横向走k步。你可以简单地认为我们的目标就是从第0行走到第n+1行，起点和终点可以是在第0行和第n+1行的任意位置，当然第0行和第n+1行都是没有弹幕的。

然而这是号称不可能的弹幕结界，所以咲夜很可能无法穿过这片弹幕，所以咲夜准备了一个只能使用一次的技能，纵向穿越，她可以从任意位置直接穿越到另外任意一行的同一个位置(所在列不变)，当然她只能向下穿越，不能向上穿越。穿越的距离越远，耗费的资源自然越多，所以她想知道最短的穿越距离，才能使她成功通过这片弹幕区。

输入包含多组数据。

对于每组数据：

第一行输入三个整数n,m,k,如上所述。

接下下输入一个n×m的矩阵，’.’表示当前这格没有子弹，是安全的，’x’表示这各有子弹，禁止通行。

N<=1000,k<=m<=1000

对于每组数据输出一个整数，表示最短的穿越距离。

6 5 2
x.x..
..xx.
.xxx.
xx.xx
xx..x
..x.x
4 4 1
.xxx
.xxx
...x
xx.x

3
2

对于第一组样例，最优解是从第一行第二列走到第三行第一列，然后跳到第6行第一列，穿越距离为(6 – 3) = 3。

long long类型请用%I64d输出