#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>

#define ll long long
using namespace std;

char s[4][505][505];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int dist[4][505][505];
int cnt[4][505][505];
int n;
void change(int x){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(s[x-1][i][j]=='N'){
                s[x][i][j]='E';
            }
            else if(s[x-1][i][j]=='E'){
                s[x][i][j]='S';
            }
            else if(s[x-1][i][j]=='S'){
                s[x][i][j]='W';
            }
            else if(s[x-1][i][j]=='W'){
                s[x][i][j]='N';
            }
            else s[x][i][j]=s[x-1][i][j];
        }
    }
}

inline bool judge(int m, int x, int y){
    if(x<0||x>=n||y<0||y>=n) return false;
    if(s[m][x][y]=='#') return false;
    return true;
}

void change2(int dir, int m, int x, int y){
    if(judge(m,x,y)){
        s[m][x][y]='x';
        x = x + dx[dir];
        y = y + dy[dir];
    }
    if(judge(m,x,y)){
        s[m][x][y]='x';
    }
}
pair<int,int> Start, End;
struct State{
    pair<int,int> here;
    int step;
    State(pair<int,int> here, int step):here(here),step(step){}
    bool operator > (const State &r) const {
        return step>r.step;
    }
};
priority_queue<State,vector<State>,greater<State> > q;
int bfs(){
    while(!q.empty()) q.pop();
    memset(dist,0x3f,sizeof dist);
    memset(cnt,0,sizeof cnt);
    dist[0][Start.first][Start.second]=0;
    q.push(State(Start,0));
    pair<int,int> mary;
    while(!q.empty()){
        State u = q.top();
        q.pop();
        int step = u.step;
//        cout<<u.here.first<<" "<<u.here.second<<" "<<step<<endl;
        if(End==u.here){
            //while(!q.empty()) u = q.top(), printf("%d %d %d\n",u.here.first,u.here.second,u.step), q.pop();
            return step;
        }
        int z = step%4;
        for(int i=0; i<4; i++){
            int x = u.here.first+dx[i];
            int y = u.here.second+dy[i];
            if(judge(z,x,y)){
                if(s[z][x][y]=='x'||s[z][u.here.first][u.here.second]=='x'){
                    if(step+3<dist[z][x][y]){
                        dist[z][x][y]=step+3;
                        mary = make_pair(x,y);
                        q.push(State(mary,step+3));
                    }
                }
                else{
                    if(step+1<dist[z][x][y]){
                        dist[z][x][y]=step+1;
                        mary = make_pair(x,y);
                        q.push(State(mary,step+1));
                    }
                }
            }
        }
        if(cnt[z][u.here.first][u.here.second]<4){
            q.push(State(u.here,step+1));
            cnt[z][u.here.first][u.here.second]++;
        }
    }
    return -1;
}

int main(){
    freopen("/home/acm/code/input.txt","r", stdin);

    int t, cs=1;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i = 0; i<n; i++){
            scanf("%s",s[0][i]);
            for(int j=0; j<n; j++){
                if(s[0][i][j]=='M'){
                    Start = make_pair(i,j);
                    s[0][i][j] = '.';
                }
                if(s[0][i][j]=='T'){
                    End = make_pair(i,j);
                    s[0][i][j] = '.';
                }
            }

        }

        for(int i=1; i<4; i++){
            change(i);
        }
        for(int k=0; k<4; k++){
            for(int i = 0; i < n; i++){
                for(int j=0; j<n; j++){
                    if(s[k][i][j]=='N'){
                        change2(0,k,i,j);
                    }
                    if(s[k][i][j]=='E'){
                        change2(1,k,i,j);
                    }
                    if(s[k][i][j]=='S'){
                        change2(2,k,i,j);
                    }
                    if(s[k][i][j]=='W'){
                        change2(3,k,i,j);
                    }
                }

            }
//            for(int i=0; i<n; i++){
//                for(int j=0; j<n; j++){
//                    putchar(s[k][i][j]);
//                }
//                puts("");
//            }
//            puts("");

        }
        printf("Case #%d: ",cs++);
        int temp = bfs();
        if(temp==-1) puts("-1");
        else printf("%d\n",temp);
    }


}