/*
剪枝：四秒后状态会变得和原来一样，所以四秒后如果再经过这个点肯定不是最优的舍去
易错点：在一个是从.到.这两个点都没有被照到并且不是摄像机，也可能需要等3秒，因为后面的结果可能再这三秒中发生改变，要单独判断
*/
#include<stdio.h>
#include<queue>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 510
char s[N][N];
struct node {
int x,y,time;
friend bool operator<(node a,node b) {//优先队列
return a.time>b.time;//从小到大出队
}
}ss,tt,next,cu;
int ma[N][N][4],n;
int judge(int x,int y) {
if(x>=1&&x<=n&&y>=1&&y<=n)
return 1;
return 0;
}
void update(int i,int j,char ch) {//存关于时间的状态
if(ch=='N') {
if(judge(i-1,j))ma[i-1][j][0]=1;
if(judge(i,j+1))ma[i][j+1][1]=1;
if(judge(i+1,j))ma[i+1][j][2]=1;
if(judge(i,j-1))ma[i][j-1][3]=1;
}
if(ch=='W') {
if(judge(i,j-1))ma[i][j-1][0]=1;
if(judge(i-1,j))ma[i-1][j][1]=1;
if(judge(i,j+1))ma[i][j+1][2]=1;
if(judge(i+1,j))ma[i+1][j][3]=1;
}
if(ch=='S') {
if(judge(i+1,j))ma[i+1][j][0]=1;
if(judge(i,j-1))ma[i][j-1][1]=1;
if(judge(i-1,j))ma[i-1][j][2]=1;
if(judge(i,j+1))ma[i][j+1][3]=1;
}
if(ch=='E') {
if(judge(i,j+1))ma[i][j+1][0]=1;
if(judge(i+1,j))ma[i+1][j][1]=1;
if(judge(i,j-1))ma[i][j-1][2]=1;
if(judge(i-1,j))ma[i-1][j][3]=1;
}
}
int dis[4][2]={1,0,-1,0,0,1,0,-1},vis[N][N][5];
int bfs() {
int i,xx,yy;
priority_queue<node>q;
memset(vis,0,sizeof(vis));
ss.time=0;
q.push(ss);
while(!q.empty()) {
ss=q.top();
q.pop();
if(ss.x==tt.x&&ss.y==tt.y)return ss.time;
//if(ss.time>=800000)break
cu=ss;cu.time++;//考虑不够完善，刚开始写的时候写到了for循环里面，这是不对的，因为。到。 等不超过四秒可能会有不同结果。
if(vis[cu.x][cu.y][cu.time%4]==0) {//等待，最多不超过三秒
vis[cu.x][cu.y][cu.time%4]=1;
q.push(cu);
};
for(i=0;i<4;i++) {
next.x=xx=ss.x+dis[i][0];
next.y=yy=ss.y+dis[i][1];
if(judge(xx,yy)&&s[xx][yy]!='#') {
// printf("%d %d
",xx,yy);
if(s[ss.x][ss.y]!='.'||ma[ss.x][ss.y][ss.time%4]||ma[xx][yy][ss.time%4]||s[xx][yy]!='.') {//如果当前点或者下一个点被照到，或者当前点和下一个点都是摄像机，那么移动的话需要时间+3
next.time=ss.time+3;
if(vis[next.x][next.y][next.time%4]==0) {
vis[next.x][next.y][next.time%4]=1;
q.push(next);
}
continue;
}
next.time=ss.time+1;
if(vis[xx][yy][next.time%4]==0) {//如果是.到.的话也可以不等待
vis[xx][yy][next.time%4]=1;
q.push(next);
}
}
}
}
return -1;
}
int main() {
int i,j,t,f=0;
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%s",s[i]+1);
memset(ma,0,sizeof(ma));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) {
if(s[i][j]=='M') {
s[i][j]='.';
ss.x=i;
ss.y=j;
}
else
if(s[i][j]=='T') {
s[i][j]='.';
tt.x=i;
tt.y=j;
}
else
if(s[i][j]!='.')
update(i,j,s[i][j]);
}
printf("Case #%d: %d
",++f,bfs());
}
return 0;
}