#include <stdio.h>

#define START 0
#define WALL  -1
#define CORR  -2
#define END   -3
#define SOL   -4

int m[101][101], nx, ny;


int print_maze(FILE *outF)
{
  /* Print the maze, and return the number of dots printed. */

  int ix, iy, ndots = 0;

  for (iy = 1;  iy <= ny;  ++iy) {
    for (ix = 1;  ix <= nx;  ++ix) {
      switch (m[ix][iy]) {
      case CORR:  fprintf(outF, " ");  break;
      case END:   fprintf(outF, "$");  break;
      case SOL:   fprintf(outF, ".");  ++ndots;  break;
      case START: fprintf(outF, "*");  break;
      case WALL:  fprintf(outF, "X");  break;
      default:    fprintf(outF, " ");
      }
    }
    fprintf(outF, "\n");
  }
  return ndots;
}


void read_maze(FILE *inF)
{
  int ix, iy, c = ' ';

  for (iy = 1;  iy <= ny;  ++iy) {
    while (c != '\n') c = fgetc(inF);
    for (ix = 1;  ix <= nx;  ++ix) {
      c = fgetc(inF);  
      switch (c) {
	case 'X': m[ix][iy] = WALL;   break;
	case ' ': m[ix][iy] = CORR;   break;
	case '*': m[ix][iy] = START;  break;
	case '$': m[ix][iy] = END;    break;
      }
    }
  }
}


void retrace(int ix, int iy, int n)
{
  if (n == 0) return;

  if (ix>1 && m[ix-1][iy]==n) {
    m[ix-1][iy] = SOL;  retrace(ix-1, iy, n-1);
  } else if (ix<nx && m[ix+1][iy]==n) {
    m[ix+1][iy] = SOL;  retrace(ix+1, iy, n-1);
  } else if (iy>1 && m[ix][iy-1]==n) {
    m[ix][iy-1] = SOL;  retrace(ix, iy-1, n-1);
  } else if (iy<ny && m[ix][iy+1]==n) {
    m[ix][iy+1] = SOL;  retrace(ix, iy+1, n-1);
  } 
}


int check(int ix, int iy, int n)
{
  if (m[ix][iy] == CORR) {
    m[ix][iy] = n;  return 1;
  }
  if (m[ix][iy] == END) {
    retrace(ix, iy, n-1);  return -10;
  }
  return 0;
}


int solve_maze(void)
{
  int ix, iy, anymore, n = 0, status;

  do {
    ++n;  anymore = 0;
    for (ix = 1;  ix <= nx;  ++ix) {
      for (iy = 1;  iy <= ny;  ++iy) {
	if (m[ix][iy] == n-1) {
	  status = 0;
	  if (ix > 1)  status += check(ix-1,iy,n); 
	  if (ix < nx) status += check(ix+1,iy,n); 
	  if (iy > 1)  status += check(ix,iy-1,n); 
	  if (iy < ny) status += check(ix,iy+1,n); 
	  if (status < 0) return 1;
	  if (status) anymore = status;
	}
      }
    }
  } while (anymore);

  return 0;
}


int main(void)
{
  FILE *inF  = fopen("maze.in", "r"), 
       *outF = fopen("maze.out", "w");
  int  n, i, ok, nsteps;

  fscanf(inF, "%d", &n);
  for (i = 1;  i <= n;  ++i) {
    fscanf(inF, "%d%d", &nx, &ny);  
    read_maze(inF);  ok = solve_maze();
    nsteps = print_maze(outF)+1;
    if (ok) fprintf(outF, "The optimal path is %d steps.\n", nsteps);
    else    fprintf(outF, "This maze has no solutions.\n");
  }

  fclose(inF);  fclose(outF);
  return 0;
}