Farmer John cambió una de sus vacas por la que Farmer Don llama «The Knight». Salta como caballo de ajedrez: dos casillas de lado y una arriba, o dos abajo y una de lado, etc. No aterriza en rocas ni árboles, pero recorre bien el pastizal de $X$ por $Y$ casillas ($1 \le X \le 150$; $1 \le Y \le 150$).

«The Knight» ama el heno. Dado el mapa del inicio, árboles, arbustos, rocas y otros obstáculos y una paca de heno, determina cuántos saltos necesita. K marca la vaca, * obstáculos, H heno. Mapa típico:

                    11 | . . . . . . . . . .
                    10 | . . . . * . . . . . 
                     9 | . . . . . . . . . . 
                     8 | . . . * . * . . . . 
                     7 | . . . . . . . * . . 
                     6 | . . * . . * . . . H 
                     5 | * . . . . . . . . . 
                     4 | . . . * . . . * . . 
                     3 | . K . . . . . . . . 
                     2 | . . . * . . . . . * 
                     1 | . . * . . . . * . . 
                     0 ----------------------
                                           1 
                       0 1 2 3 4 5 6 7 8 9 0

El camino A, B, C, etc. llega al heno en 5 saltos (podría haber otros caminos de longitud 5):

                    11 | . . . . . . . . . .
                    10 | . . . . * . . . . .
                     9 | . . . . . . . . . .
                     8 | . . . * . * . . . .
                     7 | . . . . . . . * . .
                     6 | . . * . . * . . . F<
                     5 | * . B . . . . . . .
                     4 | . . . * C . . * E .
                     3 | .>A . . . . D . . .
                     2 | . . . * . . . . . *
                     1 | . . * . . . . * . .
                     0 ----------------------
                                           1
                       0 1 2 3 4 5 6 7 8 9 0

Pista: probablemente lo más fácil sea una cola simple primero en entrar, primero en salir, con unos cuantos arreglos paralelos.

Entrada

• Línea 1: dos enteros $X$, $Y$ separados por espacio.
• Líneas $2..Y+1$: línea $Y-i+2$, $X$ caracteres sin espacios, fila $i$ del mapa (en el orden mostrado arriba).

Salida

• Línea 1: un entero, mínimo de saltos al heno. Siempre es posible llegar.

Ejemplos

Entrada 1

10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..

Salida 1

5

Autor del problema: Rob Kolstad, 2009