#include <iostream>
#include <vector>
using namespace std;

const int Vam = 5000;
const int INF = 1 << 20;

const int px[4] = { -1,0,0,1 };
const int py[4] = { 0,-1,1,0 };

struct Situ
{
	int x;
	int y;
	int d;
}que[150];
bool serched[14][14];

vector<int> G[Vam];
int match[Vam];
bool used[Vam];

void add_edge(int u, int w);
bool dfs(int v);

int X, Y, X_Y;

int room[14][14];
int roomnum[14][14];
int pnum, dnum;
int mindistance[150][50];

bool bfs(int sx, int sy);

int main()
{
	int casen, st, p;
	char ch;
	bool flag;

	cin >> casen;

	while (casen--)
	{
		pnum = 0;
		dnum = 0;
		st = 0;

		for (int i = 0; i < 14; i++)
		{
			for (int j = 0; j < 14; j++)
			{
				room[i][j] = 0;
				roomnum[i][j] = 0;
			}
		}

		for (int i = 0; i < 150; i++)
		{
			for (int j = 0; j < 50; j++)
			{
				mindistance[i][j] = INF;
			}
		}

		for (int i = 0; i < Vam; i++)
		{
			G[i].clear();
			match[i] = -1;
			used[i] = false;
		}

		cin >> X >> Y;
		X_Y = X * Y;

		for (int i = 1; i <= X; i++)
		{
			for (int j = 1; j <= Y; j++)
			{
				cin >> ch;
				switch (ch)
				{
				case '.':
					room[i][j] = 1;
					roomnum[i][j] = pnum++;
					break;
				case 'D':
					room[i][j] = 2;
					roomnum[i][j] = dnum++;
					break;
				case 'X':
					room[i][j] = 0;
					break;
				}
			}
		}

		for (int i = 1; i <= X; i++)
		{
			for (int j = 1; j <= Y; j++)
			{
				if (room[i][j] == 2)
				{
					roomnum[i][j] += pnum;
				}
			}
		}

		flag = false;
		for (int i = 2; i < X; i++)
		{
			for (int j = 2; j < Y; j++)
			{
				if (room[i][j])
				{
					if (bfs(i, j))
					{
						flag = true;
					}
				}
			}
		}
		if (flag)
		{
			cout << "impossible\n";
			continue;
		}

		p = 0;
		for (st = 0; (st < X_Y) && (p < pnum); st++)
		{
			for (int i = 0; i < pnum; i++)
			{
				for (int j = 0; j < dnum; j++)
				{
					if (mindistance[i][j] - 1 <= st)
					{
						add_edge(i, pnum + st * dnum + j);
					}
				}
			}

			for (int i = 0; i < Vam; i++)
			{
				used[i] = false;
			}

			for (int i = 0; i < dnum; i++)
			{
				if (dfs(pnum + st * dnum + i))
				{
					p++;
				}
			}
		}

		cout << st << '\n';

	}
	return 0;
}

void add_edge(int u, int w)
{
	G[u].push_back(w);
	G[w].push_back(u);
	return;
}

bool dfs(int v)
{
	int u, w;

	used[v] = true;

	for (int i = 0; i < G[v].size(); i++)
	{
		u = G[v][i];
		w = match[u];

		if (w < 0)
		{
			match[v] = u;
			match[u] = v;
			return true;
		}
		else if (!used[w])
		{
			if (dfs(w))
			{
				match[v] = u;
				match[u] = v;
				return true;
			}
		}
	}

	return false;
}

bool bfs(int sx, int sy)
{
	static Situ m, s;
	int qb = 0, qf = 0;
	bool flag = true;

	for (int i = 0; i < 14; i++)
	{
		for (int j = 0; j < 14; j++)
		{
			serched[i][j] = false;
		}
	}

	s.x = sx;
	s.y = sy;
	s.d = 0;

	que[qf++] = s;

	while (qf > qb)
	{
		m = que[qb++];

		for (int i = 0; i < 4; i++)
		{
			s.x = m.x + px[i];
			s.y = m.y + py[i];
			s.d = m.d + 1;
			if ((!serched[s.x][s.y]) && room[s.x][s.y])
			{
				serched[s.x][s.y] = true;

				if (room[s.x][s.y] == 2)
				{
					mindistance[roomnum[sx][sy]][roomnum[s.x][s.y] - pnum] = s.d;
					flag = false;
				}
				else
				{
					que[qf++] = s;
				}
			}
		}
	}

	return flag;
}

/*
数据直接 Ctrl + C 复制, 再 Ctrl + V 粘贴就行

数据:

9

5 5
XDXXX
X...X
X.X.X
X...X
XXXXX

5 12
XXXXXXXXXXXX
X..........D
X.XXXXXXXXXX
X..........X
DDDDDDDDDDDD

12 12
DDDDDDDDDDDD
D..........D
D..........D
D..........D
D..........D
D..........D
D..........D
D..........D
D..........D
D..........D
D..........D
DDDDDDDDDDDD

12 12
XXXXXXXXXXDD
X..........X
X.XXXXXXXXXX
X..........X
XXXXXXXXXX.X
X..........X
X.XXXXXXXXXX
X..........X
XXXXXXXXXX.X
X..........X
X.X.X.X.X..X
XXXXXXXXXXXX

12 12
XXXXXXXXXXDX
X..........D
X.XXXXXXXXXX
X..........X
XXXXXXXXXX.X
X..........X
X.XXXXXXXXXX
X..........X
XXXXXXXXXX.X
X..........X
X.X.X.X.X..X
XXXXXXXXXXXX

12 12
XXXXXXXXXXDX
X..........D
X.XXXXXXXXXX
X..........D
XXXXXXXXXX.X
X..........X
X.XXXXXXXXXX
X..........X
XXXXXXXXXX.X
X..........X
X.X.X.X.X..X
XXXXXXXXXXDX

6 6
XDXXXX
D....D
X.X..X
X.XX.X
X...XX
XXXDXX

5 5
XXXXX
X...D
X.XXX
X...D
XXXXX

7 6
XXXXXX
X....D
XXXX.X
X....X
X.XXXX
X....X
XXDXXX


结果:

8
6
5
60
55
22
4
4
7

*/

• Re:贴个c++代码, 再贴几组数据, 建议不要用数组, 不太好估计大小 (192) 1727405069 2019-07-28 20:27:11
• Re:贴个c++代码, 再贴几组数据, 建议不要用数组, 不太好估计大小 (28) hewxuan 2019-11-24 10:22:28
• Re:贴个c++代码, 再贴几组数据, 建议不要用数组, 不太好估计大小 (5251) sf30 2020-03-03 17:31:59
  • Re:贴个c++代码, 再贴几组数据, 建议不要用数组, 不太好估计大小 (13) sf30 2020-03-03 17:32:48