咲夜需要穿过一片弹幕区，由于咲夜发动了符卡“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

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

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <climits>

#include <cstring>

#include <string>

#include <set>

#include <bitset>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <cassert>

#define rep(i,m,n) for(i=m;i<=n;i++)

#define mod 1000000007

#define inf 0x3f3f3f3f

#define vi vector<int>

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define ll long long

#define pi acos(-1.0)

#define pii pair<int,int>

#define sys system("pause")

const int maxn=1e3+;

const int N=2e5+;

using namespace std;

ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}

ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p%mod;p=p*p%mod;q>>=;}return f;}

int n,m,k,t,l[maxn][maxn],r[maxn][maxn],dp[maxn],up[maxn][maxn],dw[maxn][maxn];

char a[maxn][maxn];

int main()

{

    int i,j;

    while(~scanf("%d%d%d",&n,&m,&k))

    {

        rep(i,,n)scanf("%s",a[i]+);

        memset(dp,-,sizeof(dp));

        memset(up,,sizeof(up));

        memset(dw,,sizeof(dw));

        rep(i,,n)

        {

            rep(j,,m)

            {

                if(j==)l[i][j]=j;

                else l[i][j]=a[i][j-]!='x'?l[i][j-]:j;

                if(l[i][j]<j-k)l[i][j]=j-k;

            }

            for(j=m;j>=;j--)

            {

                if(j==m)r[i][j]=j;

                else r[i][j]=a[i][j+]!='x'?r[i][j+]:j;

                if(r[i][j]>j+k)r[i][j]=j+k;

            }

        }

        rep(i,,m)if(a[][i]=='.')up[][i]=;

        rep(i,,n)

        {

            if(i!=)

            {

                rep(j,,m)up[i][j]+=up[i][j-];

            }

            rep(j,,m)

            {

                if(up[i][j]&&a[i+][j]=='.')up[i+][l[i+][j]]++,up[i+][r[i+][j]+]--;

            }

        }

        rep(i,,m)if(a[n][i]=='.')dw[n][i]=;

        for(i=n;i>=;i--)

        {

            if(i!=n)

            {

                rep(j,,m)dw[i][j]+=dw[i][j-];

            }

            rep(j,,m)

            {

                if(dw[i][j]&&a[i-][j]=='.')dw[i-][l[i-][j]]++,dw[i-][r[i-][j]+]--;

            }

        }

        int ret=n+;

        for(i=n;i>=;i--)

        {

            rep(j,,m)

            {

                if(up[i][j])ret=min(ret,n+-i);

                if(up[i][j]&&dp[j]!=-)ret=min(ret,dp[j]-i);

                if(dw[i][j])dp[j]=i,ret=min(ret,i);

            }

        }

        rep(i,,m)if(up[n][i])ret=;

        printf("%d\n",ret);

    }

    return ;

}