/*
  BAPC'06
  evacuation Hendrik Jan Hoogeboom (2)
  Marriage Matching (Hall)
*/

#include <vector>
#include <string>
#include <queue>
#include <iostream>

using namespace std;
const int maxDim = 12,
          maxQuad = maxDim*maxDim ;

int main ()
{
  int cases,x,y,i,t,
     OK,exitFound,
     evac, deur,
     pos,
     maxT,
     dimX, dimY,  // dimensions (3 <= <= 12)
     dist[maxDim*maxDim],  // floodfill distances (positions)
     evacTel,     // number of people to be evacuated
     deurTel,     // number of doors
// people '.' are represented by their number in the order we found them
// doors  'D' by their number
     naarDeur[maxDim*maxDim][4*maxDim], 
         // naarDeur[e][d] distance from evacue 'e' to door 'd'
     rep[4*maxDim][maxDim*maxDim] ;
         // Hall matching:
         // rep[d][t]=e  door 'd' at time 't' is exit for 'e'
	   
  char   room[maxDim*maxDim];  // linear representation of room
  string regel;
  queue<int> punt;  // for computing distances
  vector<int> door, // positions of doors
            // Hall's backtrack
      hallDoor, hallTime;
  int cand,j;
  int seen[maxDim*maxDim];

  cin >> cases;
  while (cases--)
  { 
// == reading input ==
    cin >> dimY >> dimX ;
//    cout << "case " << cases << " ";
//    cout << "(" << dimX << "x" << dimY << ")" << endl;
    const int buur[4] = {-1,+1,-dimX,+dimX};
    pos = 0;       
    for ( y=0; y<dimY; y++ )
    { // put matrix linearly in array
      cin >> regel;
      for ( x=0; x<dimX; x++ )
      { 
        room[pos] = regel[x];
        pos++;
      }
    } // for y
// == counting, can be omitted == 
    evacTel = 0;
    door.clear() ;
    for ( pos=0; pos<dimY*dimX; pos++ )
    {
      if (room[pos] == 'D') door.push_back(pos);
      if (room[pos] == '.') evacTel++;   
//      cout << room[pos];
//      if (pos % dimX == dimX-1) cout << endl;
    }
    deurTel = door.size();

//    cout << "deuren: " << deurTel <<
//    "\npunten: " << evacTel << endl;

    for ( evac=0; evac<evacTel; evac++ )
      for ( deur=0; deur<deurTel; deur++ )
         naarDeur[evac][deur] = maxQuad;  // larger than max distance
	 
    if (deurTel == 0 )
    {  // NO DOORS!
      cout << "impossible" << endl; continue;
    }

// compute distances to each door
    for (deur = 0; deur<deurTel  ; deur++)
    {  
      //cout << deur << "  ";
      for ( pos=0; pos<dimY*dimX; pos++ ) dist[pos] = -1;
      pos = door[deur];
      //x = pos % dimX;
      //y = pos / dimX;
      //cout << "[" << x << "," << y << "]" << endl;
      dist[pos] = 0;
      punt.push(pos);
      while ( !punt.empty() )
      { pos = punt.front();
        for ( i=0; i<4; i++ ) 
        { pos = punt.front() + buur[i];    
          if ( pos<0 || pos>=dimY*dimX || dist[pos]>0 || room[pos] != '.') 
            continue;
          dist[pos] = dist[punt.front()] +1;
	  punt.push(pos);
        }
        punt.pop();
      }// while punt

      // renumber from positions to evac-number
      evac=0;
      for ( pos=0; pos<dimY*dimX; pos++ )
      {  // cout << room[y][x];
        if (room[pos] == '.') 
	{ if ( dist[pos]>0 ) naarDeur[evac][deur] = dist[pos];   
	    evac++;
	}
      } // naarDeur[evacNum]    
    } //elke deur
// exit reachable?
    evac=0; OK = 1;
    for ( pos=0; pos<dimY*dimX; pos++ )
    if (room[pos] == '.')
    {
      exitFound = 0;
      for (deur=0; deur<deurTel ; deur++)
        if ( naarDeur[evac][deur]<maxQuad ) { exitFound=1; break; }
      if (exitFound==0) { OK = 0;  break;}    
      evac++;
    }
    if (OK == 0 )
    {  // TRAPPED!
      cout << "impossible" << endl; continue;
    }
    if (deurTel==1) 
    {  //  SINGLE DOOR!
      cout  << evacTel  << endl; continue;
    }
    
// find representatives
// using Hall's matching
    for (deur=0; deur<deurTel ; deur++)
      for (t=0; t<dimX*dimY ; t++)
        rep[deur][t] = -1 ;
    evac = 0;
    maxT = 1;
    while (evac<evacTel)
    { // find next evacuation
      t=0; OK=0;
      // OK means we have a time-slot for current evac
      while ( !OK )
      { // try available doors for successive time-slots
        t++;
	if (t>maxT) 
        { // no slot: try Hall's backtracking
          hallDoor.clear();
          hallTime.clear();
          // ain't seen nothing yet
          for (j=0; j<evacTel; j++) seen[j] = -999;

          i=-1; cand=evac;
          // push 'legal' slots for evac (none of these available)
          for (t=1; t<=maxT; t++) for (deur=0; deur<deurTel; deur++)
            if ( t>=naarDeur[cand][deur] )
            { hallDoor.push_back(deur); hallTime.push_back(t); 
              seen[rep[deur][t]] = -1;
            }
          while (i < int(hallDoor.size()-1) && !OK )
          {
            i++;
            cand = rep[ hallDoor[i] ][ hallTime[i] ];
            // push NEW legal slots UNTIL available found
            for (t=1; t<=maxT; t++) for (deur=0; deur<deurTel; deur++)
              if ( t>=naarDeur[cand][deur] )
                if ( rep[deur][t]<0 ) // available
                { OK=1; 
                  hallDoor.push_back(deur); hallTime.push_back(t);
                  break; 
                }
                else 
                {
                  if ( seen[ rep[deur][t] ] < -500 ) // new: push & mark
                  { hallDoor.push_back(deur); hallTime.push_back(t);
                    seen[ rep[deur][t] ] = i ; // legal for whom
                  }
                }
            }
           
            if (OK) // backtrack & re-assign, start with last one pushed
            { deur = hallDoor.back(); t = hallTime.back();
              while (i>=0)
              { 
                rep[deur][t] = rep[hallDoor[i]][hallTime[i]];
                deur = hallDoor[i]; t = hallTime[i];
                i = seen[rep[deur][t]];
              }
              rep[deur][t] = evac;
            }
            else // not found: update time bound
            { maxT++; }
        }
        else // (t<=maxT)
        {
          for (deur=0; deur<deurTel; deur++)
	  if ( t>=naarDeur[evac][deur] && rep[deur][t] <0 )
	  { // available!
	    rep[deur][t] = evac;
	    OK = 1;
	    break;
	  } 
        } // else (t<=maxT)
      } // !OK
      evac++; 
    } // evac<evacTel

    cout  << maxT << endl ; //<< "#HALL "
        
  }// cases
}
