#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<map>
#include<cctype>
using namespace std;
int n,m,b[][]={,-,,,-,,,},minn,visited[][],vis[][];
char a[][];
struct monkey
{
int x,y,step;
};
queue<monkey>Q;
void pretreatment(int x,int y,char b,char c) //坐标 和 该名称 和 另一人名称
{
for(int i=x+;i<m&&a[y][i]!='X'&&a[y][i]!=c;i++)
a[y][i]=(a[y][i]=='d'?'O':b+);
for(int i=x-;i>=&&a[y][i]!='X'&&a[y][i]!=c;i--)
a[y][i]=(a[y][i]=='d'?'O':b+);
for(int i=y+;i<n&&a[i][x]!='X'&&a[i][x]!=c;i++)
a[i][x]=(a[i][x]=='d'?'O':b+);
for(int i=y-;i>=&&a[i][x]!='X'&&a[i][x]!=c;i--)
a[i][x]=(a[i][x]=='d'?'O':b+);
}
queue<monkey>W;
void BFSMORE(int x,int y,int step,char c)
{
monkey q={x,y,step};
W.push(q);
while(!W.empty())
{
monkey e=W.front();
W.pop();
for(int i=;i<;i++)
{
q.x=e.x+b[i][],q.y=e.y+b[i][];
if(a[q.y][q.x]!='X'&&a[q.y][q.x]!='D'&&a[q.y][q.x]!='E'&&q.x>=&&q.x<m&&q.y>=&&q.y<n&&!vis[q.y][q.x])
{
vis[q.y][q.x]=;
q.step=e.step+;
W.push(q);
if(a[q.y][q.x]==c||a[q.y][q.x]=='O')
{
minn=minn>q.step?q.step:minn;
while(!W.empty())
W.pop();
break;
}
}
}
}
}
void BFS(int x,int y)
{
monkey q={x,y,};
if(a[y][x]=='O')
{
minn=;
return ;
}
if(a[y][x]=='d')
{
memset(vis,,sizeof(vis));
BFSMORE(x,y,,'e');
}
if(a[y][x]=='e')
{
memset(vis,,sizeof(vis));
BFSMORE(x,y,,'d');
}
Q.push(q);
while(!Q.empty())
{
monkey e=Q.front();
Q.pop();
for(int i=;i<;i++)
{
q.x=e.x+b[i][],q.y=e.y+b[i][];
if(a[q.y][q.x]!='X'&&a[q.y][q.x]!='D'&&a[q.y][q.x]!='E'&&q.x>=&&q.x<m&&q.y>=&&q.y<n&&!visited[q.y][q.x])
{
q.step=e.step+;
Q.push(q);
visited[q.y][q.x]=;
if(a[q.y][q.x]=='O')
{
minn=minn>q.step?q.step:minn;
}
if(a[q.y][q.x]=='d')
{
memset(vis,,sizeof(vis));
BFSMORE(q.x,q.y,q.step,'e');
}
if(a[q.y][q.x]=='e')
{
memset(vis,,sizeof(vis));
BFSMORE(q.x,q.y,q.step,'d');
}
}
}
}
}
int main()
{
int sx,sy,dx,dy,ex,ey,t,count1=;
while(scanf("%d%d%d",&n,&m,&t)!=EOF)
{
minn=t+;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
scanf(" %c",&a[i][j]);
if(a[i][j]=='S')
{
sx=j;
sy=i;
}
if(a[i][j]=='D')
{
dx=j;
dy=i;
}
if(a[i][j]=='E')
{
ex=j;
ey=i;
}
}
}
pretreatment(dx,dy,'D','E');
pretreatment(ex,ey,'E','D');
memset(visited,,sizeof(visited));
visited[sy][sx]=;
BFS(sx,sy);
printf("Case %d:\n",++count1);
if(minn<=t)
printf("%d\n",minn);
else
printf("-1\n");
}
return ;
}
