La abuelita Caperucita
Estamos en 2318. Los avances en ciencia y tecnología han hecho posible que los personajes de los cuentos sean personas de carne y hueso. No obstante, durante la transmogrificación de Caperucita Roja, hubo una distorsión de tiempo en la undécima dimensión haciendo que la joven Caperucita saliera como una abuelita rozando los 100 años. Por el contrario, el lobo feroz no tuvo ese problema y salió exactamente con la misma mentalidad, ganas y hambre de comerse a Caperucita.
Caperucita sigue fiel a sus raíces y vive en mitad de un bosque. Cuando se ha dado cuenta de que el lobo viene a por ella, se ha puesto a buscar ayuda desesperadamente para proteger su vida, pues ya no tiene la misma agilidad que antes. Por suerte, el cazador también mantiene su juventud y vitalidad y se ha ofrecido para colocar trampas que bloqueen el camino del lobo a su casa. Como no hay mucho tiempo que perder, necesitan saber cuántas hay que poner como mínimo.
Veremos el bosque como una cuadrícula con algunas celdas transitables y otras no (por tener árboles). El lobo puede moverse desde una casilla a cada una de sus cuatro casillas adyacentes siempre que éstas sean transitables. Consideraremos que Caperucita está protegida si el lobo no puede llegar a la casilla en la que está. Eso sí, ten en cuenta que en las 4 casillas adyacentes a Caperucita no podemos colocar trampas; ella podría accidentalmente moverse y pisarlas.
Entrada
La primera línea contiene el número de casos de prueba que vendrán a continuación.
Cada uno de ellos tiene una primera línea con dos valores N y M (2 ≤ N, M ≤ 30), el número de filas y columnas de la cuadrícula, respectivamente. A continuación sigue la descripción de la cuadrícula, compuesta por N líneas de longitud M donde cada celda puede tomar uno de los cuatro valores: celda ocupada por Caperucita (C), por el lobo (L), celda transitable (.) o celda no transitable (#).
Salida
Por cada caso de prueba se escribirá una única línea con el número mínimo de trampas que deberá poner el cazador para proteger a Caperucita. Las trampas solo pueden colocarse en las celdas libres.
Si es imposible proteger a Caperucita, se escribirá IMPOSIBLE.
Entrada de ejemplo
3 4 5 ...C. ...#. ##... ..L.. 3 3 C.# ... #.L 4 6 ###### ##..## #.LC.# ######
Salida de ejemplo
2 1 IMPOSIBLE