/*
  [BAPC'06] EVACUATION
  by: Jan Kuipers
*/

using namespace std;

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

const int dy[4] = { -1,+1, 0, 0 };
const int dx[4] = {  0, 0,-1,+1 };

int N;
vector<int> u;
vector<vector<int> > c;

int match (int n) {
  if (n==0) return 1;
  u[n]=1;

  for (int i=0; i<N; i++)
    if (c[n][i] && !u[i] && match(i)) {
      c[n][i]--;
      c[i][n]++;
      return 1;
    }

  return 0;
}

int main () {

  int runs;
  cin>>runs;
  while (runs--) {
    int Y,X;
    cin>>Y>>X;
    vector<string> m(Y);
    for (int y=0; y<Y; y++)
      cin>>m[y];

    int D=0, P=0;
    for (int y=0; y<Y; y++)
      for (int x=0; x<X; x++) {
	if (m[y][x]=='D') D++;
	if (m[y][x]=='.') P++;
      }

    vector<vector<int> > dist(D, vector<int>(P));

    int d=0;
    
    for (int y=0; y<Y; y++)
      for (int x=0; x<X; x++)
	if (m[y][x]=='D') {
	  vector<int> b(Y*X,-1);
	  queue<int> q;
	  q.push(y);
	  q.push(x);
	  q.push(0);
	  while (!q.empty()) {
	    int yy=q.front(); q.pop();
	    int xx=q.front(); q.pop();
	    int dd=q.front(); q.pop();
	    if (b[yy*X+xx]!=-1) continue;
	    b[yy*X+xx]=dd;
	    for (int i=0; i<4; i++) {
	      int ny=yy+dy[i], nx=xx+dx[i];
	      if (ny<0||ny>=Y||nx<0||nx>=X) continue;
	      if (m[ny][nx]!='.') continue;
	      q.push(ny);
	      q.push(nx);
	      q.push(dd+1);
	    }
	  }

	  int p=0;
	  for (int y2=0; y2<Y; y2++)
	    for (int x2=0; x2<X; x2++)
	      if (m[y2][x2]=='.')
		dist[d][p++] = b[y2*X+x2];
	  
	  d++;
	}

    int ok=1;
    for (int p=0; p<P; p++) {
      int pok=0;
      for (int d=0; d<D; d++)
	if (dist[d][p]!=-1) pok=1;
      if (!pok) ok=0;
    }

    if (!ok) {
      cout<<"impossible"<<endl;
      continue;
    }

    N=P+1;
    vector<int> empty(1+P+D*X*Y);
    c=vector<vector<int> >(P+1, empty);
    for (int i=1; i<=P; i++) c[i][0]=1;

    int M=0, T;
    for (T=1; M<P; T++)

      for (int d=0; d<D; d++) {
	c.push_back(empty);
	N++;
	for (int p=0; p<P; p++)
	  if (dist[d][p]!=-1 && dist[d][p]<=T) c.back()[p+1]=1;
	  
	u=vector<int>(N,0);
	if (match(N-1)) M++;
      }

    cout<<T-1<<endl;
  }

  return 0;
}
