/* 3442 */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <queue>

 using namespace std;

 #define MAXN 55

 typedef struct node_t {

     int x, y;

     int s, v;

     node_t() {}

     node_t(int xx, int yy, int ss, int vv) {

         x = xx; y = yy; s = ss; v = vv;

     }

     friend bool operator <(const node_t &a, const node_t &b) {

         return a.v > b.v;

     }

 } node_t;

 char map[MAXN][MAXN];

 char hurt[MAXN][MAXN][];

 bool visit[MAXN][MAXN][];

 int ls[] = {, , , , };

 int bx, by, ex, ey;

 int dir[][] = {

     {-,},{,},{,-},{,}

 };

 int n, m;

 int abs(int x) {

     return x< ? -x:x;

 }

 bool check(int x, int y) {

     return x< || x>=n || y< || y>=m;

 }

 bool invalid(char ch) {

     return !(ch=='$' || ch=='!' || ch=='C' || ch=='.');

 }

 int Manh(int x0, int y0, int x1, int y1) {

     return abs(x0-x1) + abs(y0-y1);

 }

 void init() {

     int i, j, k, h, l;

     int x, y, z;

     memset(hurt, , sizeof(hurt));

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

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

             if (map[i][j] == '$') {

                 bx = i;

                 by = j;

             } else if (map[i][j] == '!') {

                 ex = i;

                 ey = j;

             } else if (map[i][j]=='#' || map[i][j]=='.') {

                 continue;

             } else if (map[i][j]>='A' && map[i][j]<='E'){

                 z = map[i][j] - 'A';

                 h = z + ;

                 l = ls[z];

                 for (x=i-l; x<=i+l; ++x) {

                     for (y=j-l; y<=j+l; ++y) {

                         if (check(x, y) || Manh(x,y,i,j)>l)

                             continue;

                         hurt[x][y][z] = h;

                     }

                 }

             }

         }

     }

 }

 int bfs() {

     int i, j, k;

     int x=bx, y=by, s=, v=;

     node_t nd;

     priority_queue<node_t> Q;

     memset(visit, false, sizeof(visit));

     visit[x][y][s] = true;

     Q.push(node_t(x, y, s, v));

     while (!Q.empty()) {

         nd = Q.top();

         if (nd.x==ex && nd.y==ey)

             return nd.v;

         Q.pop();

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

             x = nd.x + dir[i][];

             y = nd.y + dir[i][];

             s = nd.s;

             v = nd.v;

             if (check(x, y) || invalid(map[x][y]) || visit[x][y][s])

                 continue;

             visit[x][y][s] = true;

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

                 k = <<j;

                 if (hurt[x][y][j] && (s&k)==) {

                     v += hurt[x][y][j];

                     s |= k;

                 }

             }

             Q.push(node_t(x, y, s, v));

         }

     }

     return -;

 }

 int main() {

     int t, tt;

     int i, j, k;

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

     #endif

     scanf("%d", &t);

     for (tt=; tt<=t; ++tt) {

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

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

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

         init();

         k = bfs();

         printf("Case %d: %d\n", tt, k);

     }

     return ;

 }