import java.util.*;
public class Main {
static class IntPair{
int x, y;
public IntPair(int x, int y) {
this.x = x;
this.y = y;
}
}
static class Edge {
int t, rev, cap, f;
public Edge(int t, int rev, int cap) {
this.t = t;
this.rev = rev;
this.cap = cap;
}
}
public static List<Edge>[] createGraph(int nodes) {
List
<Edge
>[] graph
= new List[nodes
]; for (int i = 0; i < nodes; i++)
graph[i] = new ArrayList<>();
return graph;
}
public static void addEdge(List<Edge>[] graph, int s, int t, int cap) {
graph[s].add(new Edge(t, graph[t].size(), cap));
graph[t].add(new Edge(s, graph[s].size() - 1, 0));
}
static boolean dinicBfs(List<Edge>[] graph, int src, int dest, int[] dist) {
dist[src] = 0;
int[] Q = new int[graph.length];
int sizeQ = 0;
Q[sizeQ++] = src;
for (int i = 0; i < sizeQ; i++) {
int u = Q[i];
for (Edge e : graph[u]) {
if (dist[e.t] < 0 && e.f < e.cap) {
dist[e.t] = dist[u] + 1;
Q[sizeQ++] = e.t;
}
}
}
return dist[dest] >= 0;
}
static int dinicDfs(List<Edge>[] graph, int[] ptr, int[] dist, int dest, int u, int f) {
if (u == dest)
return f;
for (; ptr[u] < graph[u].size(); ++ptr[u]) {
Edge e = graph[u].get(ptr[u]);
if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
int df
= dinicDfs
(graph, ptr, dist, dest, e.
t,
Math.
min(f, e.
cap - e.
f)); if (df > 0) {
e.f += df;
graph[e.t].get(e.rev).f -= df;
return df;
}
}
}
return 0;
}
public static int maxFlow(List<Edge>[] graph, int src, int dest) {
int flow = 0;
int[] dist = new int[graph.length];
while (dinicBfs(graph, src, dest, dist)) {
int[] ptr = new int[graph.length];
while (true) {
int df
= dinicDfs
(graph, ptr, dist, dest, src,
Integer.
MAX_VALUE); if (df == 0)
break;
flow += df;
}
}
return flow;
}
static int trad(int m, int x, int y){
return x*m+y;
}
public static void main
(String[] args
) { Scanner in
= new Scanner
(System.
in); int t = in.nextInt();
while (t-->0){
int n = in.nextInt();
int m = in.nextInt();
char[][]grid = new char[n][m];
IntPair l = new IntPair(0, 0);
IntPair c = new IntPair(0, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = s.charAt(j);
if(grid[i][j]=='L') l = new IntPair(i, j);
else if(grid[i][j]=='C') c = new IntPair(i,j);
}
}
HashSet<Integer> set = new HashSet<>();
set.add(trad(m, c.x, c.y));
set.add(trad(m, c.x-1, c.y));
set.add(trad(m, c.x+1, c.y));
set.add(trad(m, c.x, c.y-1));
set.add(trad(m, c.x, c.y+1));
set.add(trad(m, l.x, l.y));
List<Edge>[] graph = createGraph(2*n*m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(grid[i][j]!='#'){
int q = (set.contains(trad(m,i,j)))?5:1;
addEdge(graph, trad(m, i, j), trad(m, i, j)+n*m, q);
//Arriba
if(i>0&&grid[i-1][j]!='#'){
int k = (set.contains(trad(m,i-1,j)))?5:1;
addEdge(graph, trad(m, i, j)+n*m,trad(m,i-1,j), k);
}
//Abajo
if(i<n-1&&grid[i+1][j]!='#'){
int k = (set.contains(trad(m,i+1,j)))?5:1;
addEdge(graph, trad(m, i, j)+n*m,trad(m,i+1,j),k);
}
//Izquierda
if(j>0&&grid[i][j-1]!='#'){
int k = (set.contains(trad(m,i,j-1)))?5:1;
addEdge(graph, trad(m, i, j)+n*m,trad(m,i,j-1), k);
}
//Derecha
if(j<m-1&&grid[i][j+1]!='#'){
int k = (set.contains(trad(m,i,j+1)))?5:1;
addEdge(graph, trad(m, i, j)+n*m,trad(m,i,j+1), k);
}
}
}
}
int sol = maxFlow(graph, trad(m, l.x, l.y), trad(m, c.x, c.y));
if(sol<=4){
}
else{
System.
out.
println("IMPOSIBLE"); }
}
}
}
aW1wb3J0IGphdmEudXRpbC4qOwoKcHVibGljIGNsYXNzIE1haW4gewogICAgc3RhdGljIGNsYXNzIEludFBhaXJ7CiAgICAgICAgaW50IHgsIHk7CgogICAgICAgIHB1YmxpYyBJbnRQYWlyKGludCB4LCBpbnQgeSkgewogICAgICAgICAgICB0aGlzLnggPSB4OwogICAgICAgICAgICB0aGlzLnkgPSB5OwogICAgICAgIH0KICAgIH0KCiAgICBzdGF0aWMgY2xhc3MgRWRnZSB7CiAgICAgICAgaW50IHQsIHJldiwgY2FwLCBmOwoKICAgICAgICBwdWJsaWMgRWRnZShpbnQgdCwgaW50IHJldiwgaW50IGNhcCkgewogICAgICAgICAgICB0aGlzLnQgPSB0OwogICAgICAgICAgICB0aGlzLnJldiA9IHJldjsKICAgICAgICAgICAgdGhpcy5jYXAgPSBjYXA7CiAgICAgICAgfQogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgTGlzdDxFZGdlPltdIGNyZWF0ZUdyYXBoKGludCBub2RlcykgewogICAgICAgIExpc3Q8RWRnZT5bXSBncmFwaCA9IG5ldyBMaXN0W25vZGVzXTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG5vZGVzOyBpKyspCiAgICAgICAgICAgIGdyYXBoW2ldID0gbmV3IEFycmF5TGlzdDw+KCk7CiAgICAgICAgcmV0dXJuIGdyYXBoOwogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBhZGRFZGdlKExpc3Q8RWRnZT5bXSBncmFwaCwgaW50IHMsIGludCB0LCBpbnQgY2FwKSB7CiAgICAgICAgZ3JhcGhbc10uYWRkKG5ldyBFZGdlKHQsIGdyYXBoW3RdLnNpemUoKSwgY2FwKSk7CiAgICAgICAgZ3JhcGhbdF0uYWRkKG5ldyBFZGdlKHMsIGdyYXBoW3NdLnNpemUoKSAtIDEsIDApKTsKICAgIH0KCiAgICBzdGF0aWMgYm9vbGVhbiBkaW5pY0JmcyhMaXN0PEVkZ2U+W10gZ3JhcGgsIGludCBzcmMsIGludCBkZXN0LCBpbnRbXSBkaXN0KSB7CiAgICAgICAgQXJyYXlzLmZpbGwoZGlzdCwgLTEpOwogICAgICAgIGRpc3Rbc3JjXSA9IDA7CiAgICAgICAgaW50W10gUSA9IG5ldyBpbnRbZ3JhcGgubGVuZ3RoXTsKICAgICAgICBpbnQgc2l6ZVEgPSAwOwogICAgICAgIFFbc2l6ZVErK10gPSBzcmM7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBzaXplUTsgaSsrKSB7CiAgICAgICAgICAgIGludCB1ID0gUVtpXTsKICAgICAgICAgICAgZm9yIChFZGdlIGUgOiBncmFwaFt1XSkgewogICAgICAgICAgICAgICAgaWYgKGRpc3RbZS50XSA8IDAgJiYgZS5mIDwgZS5jYXApIHsKICAgICAgICAgICAgICAgICAgICBkaXN0W2UudF0gPSBkaXN0W3VdICsgMTsKICAgICAgICAgICAgICAgICAgICBRW3NpemVRKytdID0gZS50OwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBkaXN0W2Rlc3RdID49IDA7CiAgICB9CgogICAgc3RhdGljIGludCBkaW5pY0RmcyhMaXN0PEVkZ2U+W10gZ3JhcGgsIGludFtdIHB0ciwgaW50W10gZGlzdCwgaW50IGRlc3QsIGludCB1LCBpbnQgZikgewogICAgICAgIGlmICh1ID09IGRlc3QpCiAgICAgICAgICAgIHJldHVybiBmOwogICAgICAgIGZvciAoOyBwdHJbdV0gPCBncmFwaFt1XS5zaXplKCk7ICsrcHRyW3VdKSB7CiAgICAgICAgICAgIEVkZ2UgZSA9IGdyYXBoW3VdLmdldChwdHJbdV0pOwogICAgICAgICAgICBpZiAoZGlzdFtlLnRdID09IGRpc3RbdV0gKyAxICYmIGUuZiA8IGUuY2FwKSB7CiAgICAgICAgICAgICAgICBpbnQgZGYgPSBkaW5pY0RmcyhncmFwaCwgcHRyLCBkaXN0LCBkZXN0LCBlLnQsIE1hdGgubWluKGYsIGUuY2FwIC0gZS5mKSk7CiAgICAgICAgICAgICAgICBpZiAoZGYgPiAwKSB7CiAgICAgICAgICAgICAgICAgICAgZS5mICs9IGRmOwogICAgICAgICAgICAgICAgICAgIGdyYXBoW2UudF0uZ2V0KGUucmV2KS5mIC09IGRmOwogICAgICAgICAgICAgICAgICAgIHJldHVybiBkZjsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXR1cm4gMDsKICAgIH0KCiAgICBwdWJsaWMgc3RhdGljIGludCBtYXhGbG93KExpc3Q8RWRnZT5bXSBncmFwaCwgaW50IHNyYywgaW50IGRlc3QpIHsKICAgICAgICBpbnQgZmxvdyA9IDA7CiAgICAgICAgaW50W10gZGlzdCA9IG5ldyBpbnRbZ3JhcGgubGVuZ3RoXTsKICAgICAgICB3aGlsZSAoZGluaWNCZnMoZ3JhcGgsIHNyYywgZGVzdCwgZGlzdCkpIHsKICAgICAgICAgICAgaW50W10gcHRyID0gbmV3IGludFtncmFwaC5sZW5ndGhdOwogICAgICAgICAgICB3aGlsZSAodHJ1ZSkgewogICAgICAgICAgICAgICAgaW50IGRmID0gZGluaWNEZnMoZ3JhcGgsIHB0ciwgZGlzdCwgZGVzdCwgc3JjLCBJbnRlZ2VyLk1BWF9WQUxVRSk7CiAgICAgICAgICAgICAgICBpZiAoZGYgPT0gMCkKICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgIGZsb3cgKz0gZGY7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIGZsb3c7CiAgICB9CgogICAgc3RhdGljIGludCB0cmFkKGludCBtLCBpbnQgeCwgaW50IHkpewogICAgICAgIHJldHVybiB4Km0reTsKICAgIH0KCgogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIFNjYW5uZXIgaW4gPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pOwogICAgICAgIGludCB0ID0gaW4ubmV4dEludCgpOwogICAgICAgIHdoaWxlICh0LS0+MCl7CiAgICAgICAgICAgIGludCBuID0gaW4ubmV4dEludCgpOwogICAgICAgICAgICBpbnQgbSA9IGluLm5leHRJbnQoKTsKICAgICAgICAgICAgY2hhcltdW11ncmlkID0gbmV3IGNoYXJbbl1bbV07CiAgICAgICAgICAgIEludFBhaXIgbCA9IG5ldyBJbnRQYWlyKDAsIDApOwogICAgICAgICAgICBJbnRQYWlyIGMgPSBuZXcgSW50UGFpcigwLCAwKTsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICAgICAgICAgIFN0cmluZyBzID0gaW4ubmV4dCgpOwogICAgICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBtOyBqKyspIHsKICAgICAgICAgICAgICAgICAgICBncmlkW2ldW2pdID0gcy5jaGFyQXQoaik7CiAgICAgICAgICAgICAgICAgICAgaWYoZ3JpZFtpXVtqXT09J0wnKSBsID0gbmV3IEludFBhaXIoaSwgaik7CiAgICAgICAgICAgICAgICAgICAgZWxzZSBpZihncmlkW2ldW2pdPT0nQycpIGMgPSBuZXcgSW50UGFpcihpLGopOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIEhhc2hTZXQ8SW50ZWdlcj4gc2V0ID0gbmV3IEhhc2hTZXQ8PigpOwogICAgICAgICAgICBzZXQuYWRkKHRyYWQobSwgYy54LCBjLnkpKTsKICAgICAgICAgICAgc2V0LmFkZCh0cmFkKG0sIGMueC0xLCBjLnkpKTsKICAgICAgICAgICAgc2V0LmFkZCh0cmFkKG0sIGMueCsxLCBjLnkpKTsKICAgICAgICAgICAgc2V0LmFkZCh0cmFkKG0sIGMueCwgYy55LTEpKTsKICAgICAgICAgICAgc2V0LmFkZCh0cmFkKG0sIGMueCwgYy55KzEpKTsKICAgICAgICAgICAgc2V0LmFkZCh0cmFkKG0sIGwueCwgbC55KSk7CiAgICAgICAgICAgIExpc3Q8RWRnZT5bXSBncmFwaCA9IGNyZWF0ZUdyYXBoKDIqbiptKTsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgbTsgaisrKSB7CiAgICAgICAgICAgICAgICAgICAgaWYoZ3JpZFtpXVtqXSE9JyMnKXsKICAgICAgICAgICAgICAgICAgICAgICAgaW50IHEgPSAoc2V0LmNvbnRhaW5zKHRyYWQobSxpLGopKSk/NToxOwogICAgICAgICAgICAgICAgICAgICAgICBhZGRFZGdlKGdyYXBoLCB0cmFkKG0sIGksIGopLCB0cmFkKG0sIGksIGopK24qbSwgcSk7CiAgICAgICAgICAgICAgICAgICAgICAgIC8vQXJyaWJhCiAgICAgICAgICAgICAgICAgICAgICAgIGlmKGk+MCYmZ3JpZFtpLTFdW2pdIT0nIycpewogICAgICAgICAgICAgICAgICAgICAgICAgICAgaW50IGsgPSAoc2V0LmNvbnRhaW5zKHRyYWQobSxpLTEsaikpKT81OjE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhZGRFZGdlKGdyYXBoLCB0cmFkKG0sIGksIGopK24qbSx0cmFkKG0saS0xLGopLCBrKTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICAvL0FiYWpvCiAgICAgICAgICAgICAgICAgICAgICAgIGlmKGk8bi0xJiZncmlkW2krMV1bal0hPScjJyl7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpbnQgayA9IChzZXQuY29udGFpbnModHJhZChtLGkrMSxqKSkpPzU6MTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFkZEVkZ2UoZ3JhcGgsIHRyYWQobSwgaSwgaikrbiptLHRyYWQobSxpKzEsaiksayk7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgLy9JenF1aWVyZGEKICAgICAgICAgICAgICAgICAgICAgICAgaWYoaj4wJiZncmlkW2ldW2otMV0hPScjJyl7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpbnQgayA9IChzZXQuY29udGFpbnModHJhZChtLGksai0xKSkpPzU6MTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFkZEVkZ2UoZ3JhcGgsIHRyYWQobSwgaSwgaikrbiptLHRyYWQobSxpLGotMSksIGspOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIC8vRGVyZWNoYQogICAgICAgICAgICAgICAgICAgICAgICBpZihqPG0tMSYmZ3JpZFtpXVtqKzFdIT0nIycpewogICAgICAgICAgICAgICAgICAgICAgICAgICAgaW50IGsgPSAoc2V0LmNvbnRhaW5zKHRyYWQobSxpLGorMSkpKT81OjE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhZGRFZGdlKGdyYXBoLCB0cmFkKG0sIGksIGopK24qbSx0cmFkKG0saSxqKzEpLCBrKTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBpbnQgc29sID0gbWF4RmxvdyhncmFwaCwgdHJhZChtLCBsLngsIGwueSksIHRyYWQobSwgYy54LCBjLnkpKTsKICAgICAgICAgICAgaWYoc29sPD00KXsKICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihzb2wpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2V7CiAgICAgICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIklNUE9TSUJMRSIpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9Cg==