#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

const int INF = 1e9+;

const int MAXN = ;

int dp[MAXN][], m, n, k;///状态，当前所在的位置

char maps[][];

struct Point

{

    int x, y;

}P[], Star;

int GetLen(Point A, Point B)

{

    int len = min(abs(A.x-B.x),abs(A.y-B.y));

    len += max(abs(A.x-B.x),abs(A.y-B.y)) - len;

    return len;

}

int DFS(int sta,int x)///状态， 现在所在的位置

{

    if(dp[sta][x] != -) return dp[sta][x];

    dp[sta][x] = INF;

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

    {

        if( (sta&(<<i)) && i != x)

        {

            dp[sta][x] = min(dp[sta][x], DFS(sta-(<<x), i)+GetLen(P[x],P[i]));

        }

    }

   // printf("dp[%d][%d] = %d\n", sta, x, dp[sta][x]);

    return dp[sta][x];

}

int main()

{

    int T, cas = ;

    scanf("%d", &T);

    while(T --)

    {

        scanf("%d %d",&n, &m);

        k = ;

        memset(dp, -, sizeof(dp));

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

        {

            scanf("%s", maps[i]);

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

            {

                if(maps[i][j] == 'g')

                    P[k].x = i, P[k++].y = j;

                if(maps[i][j] == 'x')

                    Star.x = i, Star.y = j;

            }

        }

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

        {

            int sta = <<i;

            dp[sta][i] =  GetLen(Star, P[i]);

        }

        int ans = INF, Lim = (<<k)-;

        for(int i=; i<k; i++)///最后停留的位置

            ans = min(ans,DFS(Lim,i)+GetLen(Star,P[i]));

        if(k == )

            ans = ;

        printf("Case %d: %d\n", cas ++, ans);

    }

    return ;

}