Valentina explora un mundo compuesto de islas y de istmos que las conectan. El mapa es una matriz de R filas y C columnas. Cada casilla contiene:

• #: parte de una isla;
• O: istmo transitable;
• X: océano.

Las casillas de una misma isla están conectadas por los cuatro lados. Dentro de cada isla Valentina puede desplazarse gratuitamente mediante autobuses; en los istmos debe caminar. Cada casilla de istmo a la que entra cuenta como un paso. Los movimientos se realizan entre casillas adyacentes por un lado; no se atraviesa el océano.

Puede iniciar el viaje en cualquier isla. Calcula el mínimo número total de pasos que debe caminar por los istmos para visitar todas las islas al menos una vez. Hay como máximo 15 islas.

Garantía de los casos de prueba de esta reedición: existe al menos una isla y es posible visitar todas las islas utilizando las casillas transitables. El documento histórico no especifica la salida para mapas sin un recorrido que conecte todas las islas; dichos mapas no forman parte de este paquete.

La primera línea contiene R C (1 ≤ R, C ≤ 50). Las siguientes R líneas contienen C caracteres cada una (#, O o X). El número de islas no supera 15.

Imprime un único entero: el mínimo número de pasos que Valentina debe caminar en los istmos para visitar todas las islas al menos una vez.