Farmer John обменял одну из своих коров на ту, которую Farmer Don звал «The Knight». Она прыгает как шахматный конь: две клетки вбок и одну вверх, либо две вниз и одну вбок и т. п. Не может приземляться на камни и деревья, но ловко перемещается по пастбищу $X$ на $Y$ клеток ($1 \le X \le 150$; $1 \le Y \le 150$).

«The Knight» любит сено. По карте старта, деревьев, кустов, камней и прочих препятствий и стога найдите число прыжков к сену. K — корова, * — препятствия, H — стог. Типичная карта:

                    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

Путь A, B, C и т. д. достигает сена за 5 прыжков (возможны другие пути длины 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

Подсказка: вероятно, проще всего использовать обычную очередь «первым пришёл — первым вышел» из нескольких параллельных массивов.

Входные данные

• Строка 1: два целых $X$, $Y$ через пробел.
• Строки $2..Y+1$: строка $Y-i+2$ содержит $X$ символов без пробелов — ряд $i$ карты (читается в порядке показанной карты).

Выходные данные

• Строка 1: целое, минимальное число прыжков к сену. Путь всегда существует.

Примеры

Входные данные 1

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

Выходные данные 1

5

Автор задачи: Rob Kolstad, 2009