Una vez mas es la “Competencia Interna de Primera División del ICPC”, y nuestros héroes de este problemset a quienes irán conociendo mientras lo vayan leyendo, no están preparados para este!. Lo que pasó es que se dedicaron a aprender más sobre seguridad informática y redes, y dejaron de lado los algoritmos, por esa razón es sabido que no tienen ninguna oportunidad el día de hoy en la Competencia de Primera División del Instituto Científico Patito Corcho (ICPC).

Como ellos saben esto, como último recurso decidieron utilizar sus conocimientos en hacking para introducirse en las máquinas de los otros competidores, y apagarlas!. Ellos saben que esto hará que los jueces se molesten y que los expulsen de la competencia, pero como es su último año compitiendo y saben que no tienen chances de clasificar, quieren que su último concurso sea épico y recordado por siempre.. :D

Ahora, la topología de red utilizada en los laboratorios de la carrera de Ciencias de la Computación es bastante extraña ya que les gusta jugar e investigar mucho. Cada computadora está conectada con las cuatro que tiene a su alrededor, una delante, una detras, una al lado izquierdo y otra al lado derecho y cada que un trozo de información pasa entre una de las máquinas, el tiempo que le toma será tomado como “uno”. Existen algunas máquinas lentium bastante antiguas en el laboratorio, a estas el tiempo que les toma pasar la información será tomada como “dos”.

Lo que nuestros amigos juackers intentarán hacer, será enviar un script alrededor del laboratorio, para que pase por las máquinas de sus compañeros que están en la competencia y las apague!. Ellos quieren que este viaje sea el más optimo posible, así que como saben poco de algoritmia, te piden que les ayudes a encontrar el camino más corto que debe recorrer su script si empezará en la computadora de uno de ellos y pasará de máquina en máquina apagando las de sus víctimas para luego volver a la máquina del atacante.

La entrada comienza con dos enteros n y m ($1 \leq n,m \leq 10$) que indican la cantidad de filas y columnas de computadoras que tiene el laboratorio. Después de eso debes leer n filas y m columnas de caracteres, de los cuales cada uno representa lo siguiente:

• “X” Indica las computadoras objetivo a las que se debe atacar.

• “x” Es también una computadora objetivo, pero esta es antigua (lentium).

• “#” Es la computadora del atacante, de donde sale el script.

• “O” Indica las computadoras que están siendo utilizadas por otros participantes.

• “o” Es una computadora utilizada por otro participante, pero esta es antigua (lentium).

• “.” Indica que esa computadora está apagada.

  Se garantiza que no habrá mas de 16 computadoras objetivo y que siempre existe la posibilidad de atacar a todas. El atacante siempre está en una computadora rápida. Las computadoras ya atacadas se apagan, pero justo antes de apagarse envían el script a travez de la red.

  La entrada termina cuando n y m son iguales a cero.

Por cada caso de entrada, imprimir el tiempo óptimo que le tomará al script viajar desde la máquina del atacante a todas las máquinas víctimas y luego volver.