//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define haha printf("haha\n")

const int maxn =  + ;

const int inf = 0x3f3f3f3f;

char ch[maxn][maxn];

int n, m;

pair<int, int> s, t;

int rook[maxn][maxn], knight[maxn][maxn];

int r1[maxn][maxn], k1[maxn][maxn];

int r2[maxn][maxn], k2[maxn][maxn];

int dx[] = {-, -, -, , , , , -};

int dy[] = {-, , , , , -, -, -};

int bfs1(int a, int b){

    memset(rook, 0x3f, sizeof(rook));

    queue<pair<int, int> > que;

    que.push(mk(a, b));

    rook[a][b] = ;

    while (!que.empty()){

        pair<int, int> p = que.front(); que.pop();

        int x = p.fi, y = p.se;

        ///if (flag && x == s.fi && y == s.se) break;

        int lb = , rb = ;

        for (int i = x - ; i > ; i--)

            if (ch[i][y] == '#') {lb = i; break;}

        for (int i = x; i <= n; i++)

            if (ch[i][y] == '#') {rb = i; break;}

        if (rb == ) rb = n + ;

        ///lb和rb都是不能走的

        for (int i = lb + ; i < rb; i++){

            if (i != x && rook[i][y] > rook[x][y] + ){

                rook[i][y] = rook[x][y] + ;

                que.push(mk(i, y));

            }

        }

        lb = , rb = ;

        for (int i = y - ; i > ; i--)

            if (ch[x][i] == '#') {lb = i; break;}

        for (int i = y; i <= m; i++)

            if (ch[x][i] == '#') {rb = i; break;}

        if (rb == ) rb = m + ;

        for (int i = lb + ; i < rb; i++){

            if (i != y && rook[x][i] > rook[x][y] + ){

                rook[x][i] = rook[x][y] + ;

                que.push(mk(x, i));

            }

        }

    }

    return rook[s.fi][s.se];

}

int bfs2(int a, int b){

    memset(knight, 0x3f, sizeof(knight));

    queue<pair<int, int> > que;

    que.push(mk(a, b));

    knight[a][b] = ;

    while (!que.empty()){

        pair<int, int> p = que.front(); que.pop();

        int x = p.fi, y = p.se;

        ///if (flag && x == s.fi && y == s.se) break;

        for (int i = ; i < ; i++){

            int nx = x + dx[i], ny = y + dy[i];

            if (nx <=  || ny <=  || nx > n || ny > m) continue;

            if (ch[nx][ny] == '#') continue;

            if (knight[nx][ny] > knight[x][y] + ){

                knight[nx][ny] = knight[x][y] + ;

                que.push(mk(nx, ny));

            }

        }

    }

    return rook[s.fi][s.se];

}

int solve(){

    //printf("k = %d r = %d\n", k[s.fi][s.se], r[s.fi][s.se]);

    //int mini = min(r2[t.fi][t.se], k2[t.fi][t.se]);

    int mini = inf;

    for (int i = ; i <= n; i++){

        for (int j = ; j <= m; j++){

            if (ch[i][j] == '#') continue;

            if (r1[i][j] < inf && k2[i][j] < inf) mini = min(mini, r1[i][j] + k2[i][j]);

            if (k1[i][j] < inf && r2[i][j] < inf) mini = min(mini, k1[i][j] + r2[i][j]);

        }

    }

    if (mini == inf) return -;

    return mini;

}

int main(){

    int T; cin >> T;

    for (int kase = ; kase <= T; kase++){

        cin >> n >> m;

        for (int i = ; i <= n; i++){

            scanf("%s", ch[i] + );

            for (int j = ; j <= m; j++){

                if (ch[i][j] == 's') s = mk(i, j);

                if (ch[i][j] == 't') t = mk(i, j);

            }

        }

        memset(r1, inf, sizeof(r1)); memset(k1, inf, sizeof(k1));

        memset(r2, inf, sizeof(r2)); memset(k2, inf, sizeof(k2));

        bfs1(t.fi, t.se); bfs2(t.fi, t.se);

        for (int i = ; i <= n; i++)

            for (int j = ; j <= m; j++)

                r1[i][j] = rook[i][j], k1[i][j] = knight[i][j];

        bfs1(s.fi, s.se); bfs2(s.fi, s.se);

        for (int i = ; i <= n; i++)

            for (int j = ; j <= m; j++)

                r2[i][j] = rook[i][j], k2[i][j] = knight[i][j];

        printf("Case #%d: %d\n", kase, solve());

    }

    return ;

}