PIC!

PIC! es un videojuego 2D de un sólo jugador. Nuestro protagonista, de nombre PIC, debe recolectar fresas para comer con el cuidado de evitar un explosivo. A continuación se muestra un tablero de 3x3 que representa el primer nivel de juego.

P++

+*+

*+E

• Un + (más) indica una casilla vacía.
• Un * (asterisco) indica una casilla donde hay una fresa.
• Una letra P mayúscula indica la casilla vacía donde está PIC.
• Una letra E mayúscula indica la casilla donde está el explosivo.

PIC puede moverse, en un solo paso, una casilla hacia arriba, hacia abajo, hacia la izquierda o hacia la derecha; siempre y cuando no se salga del tablero. Es decir, puede moverse a las casillas adyacentes de donde se encuentra. De todas formas, si llega a ubicarse en una casilla adyacente al explosivo, morirá. El juego termina si se acaban las fresas o si PIC muere.

Dado un mapa del nivel en el que se encuentra nuestro personaje, nos preguntamos ¿cuál es la máxima cantidad de fresas que podemos recoger antes de que el juego termine? Ayúdanos escribiendo un programa que nos diga la respuesta.

Entrada

La primer línea de la entrada contiene un número entero T (1 = T = 50) que indica la cantidad de niveles que nos interesa analizar. T niveles se describen a continuación.

La descripción de cada nivel comienza con un número entero M (2 = M = 20) en una sola línea, que indica la cantidad de filas y columnas del tablero. Las siguientes M líneas describen el tablero de juego de acuerdo al ejemplo dado en el enunciado.

Salida

Por cada nivel descrito, imprima el número máximo de fresas que nuestro personaje puede recoger. A continuación, en la misma línea, imprima las posiciones de cada una de las fresas siguiendo el formato que se indica a continuación.

Cada posición se debe imprimir como una pareja de números enteros X Y separados por un espacio, tal como se muestra en la sección de ejemplos. El número X indica la fila y el número Y indica la columna. Las filas están numeradas desde 0 hasta M - 1, desde arriba hacia abajo; las columnas desde 0 hasta M - 1 también, pero desde la izquierda hacia la derecha. Además, las posiciones de las fresas se deben imprimir de manera ordenada, primero por número de fila (de menor a mayor), y luego por número de columna (de menor a mayor también).

Finalmente, debe imprimir una línea en blanco después de la salida de cada nivel.

Ejemplo de Entrada

3  
3  
P++  
+*+  
*+E  
5  
+++++  
*++++  
+++++  
+*+++  
+++PE  
3  
++E  
***  
P**

Ejemplo de Salida

2 1 1 2 0  
0  
4 1 0 1 1 2 1 2 2