#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<ctime>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-10;void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c = getchar();    x = 0;    while(!isdigit(c)) c = getchar();    while(isdigit(c))    {        x = x * 10 + c - ‘0‘;        c = getchar();    }}int T,n,m,t;char s[105][105];int sx,sy,ex,ey,dx,dy;int dir[4][2]={ {-1,0},{1,0},{0,-1},{0,1} };int f[2][105][105];int dis[105][105][4];int flag;struct X{    int a,b,st;    X(int A,int B,int ST)    {        a=A;        b=B;        st=ST;    }};bool check(int a,int b){    if(a<0||a>=n) return 0;    if(b<0||b>=m) return 0;    if(s[a][b]!=‘.‘) return 0;    return 1;}void bfs(){    queue<X>Q; int st=f[0][sx][sy]*(1<<0)+f[1][sx][sy]*(1<<1);    Q.push(X(sx,sy,st));  dis[sx][sy][st]=0;    while(!Q.empty())    {        X h=Q.front(); Q.pop();        if(h.st==3)        {            if(dis[h.a][h.b][h.st]<=t)            {                printf("%d\n",dis[h.a][h.b][h.st]);                flag=1;            }            return ;        }        for(int i=0;i<4;i++)        {            int tx=h.a+dir[i][0],ty=h.b+dir[i][1];            if(check(tx,ty)==0) continue;            int tst = h.st;            if(f[0][tx][ty]==1) tst=tst|(1<<0);            if(f[1][tx][ty]==1) tst=tst|(1<<1);            if(dis[tx][ty][tst]!=0x7FFFFFFF) continue;            dis[tx][ty][tst]=dis[h.a][h.b][h.st]+1;            Q.push(X(tx,ty,tst));        }    }}int main(){    scanf("%d",&T); int cas=1;    while(T--)    {        scanf("%d%d%d",&n,&m,&t);        for(int i=0;i<n;i++) scanf("%s",s[i]);        for(int i=0;i<n;i++)        {            for(int j=0;j<m;j++)            {                if(s[i][j]==‘S‘) sx=i,sy=j;                if(s[i][j]==‘E‘) ex=i,ey=j;                if(s[i][j]==‘D‘) dx=i,dy=j;                for(int k=0;k<4;k++) dis[i][j][k]=0x7FFFFFFF;                f[0][i][j]=f[1][i][j]=0;            }        }        s[sx][sy]=‘.‘;        for(int k=0;k<=1;k++)        {            int a,b;            for(int i=0;i<4;i++)            {                if(k==0) a=ex,b=ey;                else a=dx,b=dy;                for(int j=0;;j++)                {                    a=a+dir[i][0], b=b+dir[i][1];                    if(check(a,b)==0) break;                    f[k][a][b]=1;                }            }        }        printf("Case %d:\n",cas++);        flag=0; bfs();        if(flag==0) printf("-1\n");    }    return 0;}