Description

Se le entrega un mapa rectangular de RxC celdas que muestra una serie de pequeñas islas rodeadas por mar. Cada celda contiene agua de mar o tierra (pero no ambas). Se considera que dos celdas están conectadas si comparten un borde o se puede viajar entre esas dos celdas usando otras celdas conectadas. Una isla es un grupo máximo de celdas terrestres que están conectadas. Por ejemplo, el siguiente mapa 12x15 tiene 5 islas (pintadas en verde):

Para facilitar el viaje, los gobiernos de estas naciones isleñas desean construir una serie de puentes para conectar las islas. Cada puente conecta exactamente dos islas. El costo de construir un puente es igual al número de celdas que ocupa en el mapa. Como todos los puentes tienen alturas distintas, no se intersectan entre sí.

¿Cuál es el costo mínimo para construir los puentes necesarios para conectar todas las islas?

Para el ejemplo anterior, aquí hay una manera de construir puentes (denotados por los cuadrados grises) que minimizan el costo total:

Input specification

En la primera línea de entrada, tenemos un solo número entero T (1 ≤ T ≤ 10), el cual corresponde a la cantidad de casos de pruebas a procesar.

Cada caso de prueba consiste en dos líneas:

1. Línea 1 contiene exactamente dos número enteros R (3 ≤ R ≤ 50) y C (3 ≤ C ≤ 50), separados por un espacio.
2. Líneas 2 hasta R+1 contienen C caracteres cada una, donde el j-ésimo caracter en la i-ésima fila corresponde a la celda (i, j) del mapa. Cada caracter es '.' o 'X', representando una celda con agua o tierra respectivamente. Se garantiza que las celdas en el borde del mapa (las que se encuentran en la primera fila, la última fila, primera columna y/o última columna) contienen agua de mar.

Para cada caso, el número de islas es al menos 2 y como máximo 300.

Output specification

Por cada caso de prueba, en el orden dado en la entrada, imprime el costo mínimo de construir puentes que conecten todas las islas.

Sample input

2
12 15
...............
..X.X..........
..XXX..........
............X..
..XX...........
..X....X.......
..X....X.......
..XXX..X.......
.......X.......
........XX.....
.........X.....
...............
5 5
.....
.X...
...X.
.X...
.....

Sample output

10
3