/*
2013腾讯马拉松初赛第5场
1004 小明系列故事——捉迷藏
Time Limit: 0.2 Seconds Memory Limit: 32768K
小明的妈妈生了三个孩子，老大叫大明， 老二叫二明， 老三...， 老三自然就叫小明了。
一天，小明的妈妈带小明兄弟三人去公园玩耍，公园里面树木很多，有很多地方可以藏身， 于是他们决定玩捉迷藏。经过几轮的猜拳后，第一轮是小明来找其他两个人，游戏规则很简单：
只要小明可以在规定的时间内找到他们就算小明获胜，并且被发现的两个人猜拳决定谁在下一轮负责找人；如果在规定的时间内只找到一个人，那么没有被发现的人获胜，被找到的人下一轮负责找人；如果在规定的时间内一个人都没有找到，则小明失败了，下一轮还是他来找人。现在小明想知道，在规定时间内，自己是否可以找到所有的人，现在他想请你来帮忙计算一下。
为了简单起见，把公园看成是n行m列的矩阵，其中’S’表示小明，’D’表示大名，’E’表示二明，’X’表示障碍物，’.’表示通路。这里，我们把发现定义为，可以直接看到对方， 也就是说两个人在同一行或者同一列，并且中间没有障碍物或者没有其他人就可以看到对方。并且假设，大明，二明藏好以后就不会再改变位置，小明每个单位时间可以从当前的位置走到相邻的四个位置之一，并且不会走出公园。
Input
测试数据第一行是一个正整数T，表示有T组测试数据。
每一组测试数据首先是三个正整数n,m,t，分别表示行数、列数和规定的时间，接下来n行，每行m个上述的字符，并且保证有且只有一个’S’，一个’E’，一个’D’。
[Technical Specification]
T < 200
3 <= n, m <= 100
0 <= t <= 100
Output
每组先输出一行Case c:(c表示当前的组数，从1开始计数)；
接下来一行，如果小明可以在规定时间内找到所有的人，则输出最少需要的时间，否则输出-1。
Sample Input
3
5 6 3
XXD...
....E.
....X.
....S.
......
5 6 3
XDX...
....E.
......
....S.
......
5 6 8
XXDX..
.XEX..
......
....S.
......
Sample Output
Case 1:
-1
Case 2:
3
Case 3:
-1
*/
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <stack>
#include <deque>
using namespace std;
typedef __int64 LL;
#define eps 10e-9
#define inf 0x3f3f3f3f
const int maxn = 100 + 20;
const int mod = 1000000000 + 7;
char ma[maxn][maxn];
bool vis[maxn][maxn][2][2];
struct node {
int x, y, step;
int f1, f2;
} s_pos, d_pos, e_pos;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n, m, t;
void cheak(node &a, node b) {
if(a.x == b.x) {
int start = min(a.y, b.y), end = max(a.y, b.y), find = 0;
for(int i = start + 1; i < end; i++) {
if(ma[a.x][i] != '.') {
find = 1;
break;
}
}
if(!find) {
a.f1 = 1;
}
}
if(a.y == b.y) {
int start = min(a.x, b.x), end = max(a.x, b.x), find = 0;
for(int i = start + 1; i < end; i++) {
if(ma[i][a.y] != '.') {
find = 1;
break;
}
}
if(!find) {
a.f1 = 1;
}
}
}
void cheak2(node &a, node b) {
if(a.x == b.x) {
int start = min(a.y, b.y), end = max(a.y, b.y), find = 0;
for(int i = start + 1; i < end; i++) {
if(ma[a.x][i] != '.') {
find = 1;
break;
}
}
if(!find) {
a.f2 = 1;
}
}
if(a.y == b.y) {
int start = min(a.x, b.x), end = max(a.x, b.x), find = 0;
for(int i = start + 1; i < end; i++) {
if(ma[i][a.y] != '.') {
find = 1;
break;
}
}
if(!find) {
a.f2 = 1;
}
}
}
int bfs() {
memset(vis
, false, sizeof(vis
)); queue<node> q;
cheak(s_pos, d_pos);
cheak2(s_pos, e_pos);
vis[s_pos.x][s_pos.y][s_pos.f1][s_pos.f2] = true;
q.push(s_pos);
while(!q.empty()) {
node now = q.front();
q.pop();
if(now.f1 > 0 && now.f2 > 0) {
return now.step;
}
for(int i = 0; i < 4; i++) {
node next = now;
next.x += dx[i];
next.y += dy[i];
if(next.x >= 0 && next.x < n && next.y >= 0 && next.y < m && !vis[next.x][next.y][next.f1][next.f2]
&& ma[next.x][next.y] == '.') {
vis[next.x][next.y][next.f1][next.f2] = true;
next.step++;
if(!next.f1)
cheak(next, d_pos);
if(!next.f2)
cheak2(next, e_pos);
if(next.step <= t)
q.push(next);
}
}
}
return 10000;
}
int main() {
int T, ca = 1;
cin >> T;
while(T--) {
scanf("%d %d %d", &n
, &m
, &t
); for(int i = 0; i < n; i++)
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(ma[i][j] == 'S') {
s_pos.x = i;
s_pos.y = j;
s_pos.step = 0;
s_pos.f1 = s_pos.f2 = 0;
}
if(ma[i][j] == 'D') {
d_pos.x = i;
d_pos.y = j;
}
if(ma[i][j] == 'E') {
e_pos.x = i;
e_pos.y = j;
}
}
}
int now = bfs();
if(now
<= t
) printf("%d\n", now
);
}
return 0;
}