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