기사도 있는 소

농부 존은 자신의 소 한 마리를, 돈 농부가 "기사(The Knight)"라고 부르는 소와 맞바꾸었다. 이 소는 체스판의 나이트처럼 목장을 뛰어다닌다. 한 번 점프할 때마다 한 방향으로 두 칸, 그리고 그와 수직인 방향으로 한 칸을 움직인다(즉 "L"자 모양). 기사 소는 장애물 위에는 착지할 수 없지만, $X \times Y$ 크기의 격자로 나뉜 목장 위를 자유롭게 뛰어다닐 수 있다($1 \le X \le 150$, $1 \le Y \le 150$).

기사 소는 건초를 무척 좋아한다. 소의 출발 칸, 장애물의 위치, 건초 더미의 위치가 표시된 지도가 주어질 때, 소가 건초 더미에 도달하기 위해 필요한 최소 점프 횟수를 구하여라. 지도에서 소의 출발 칸은 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

이 지도에서 소는 출발 칸 K에서 건초 더미 H까지 최소 5번의 점프로 도달할 수 있다(길이가 5인 다른 경로도 있을 수 있다). 건초 더미에는 항상 도달할 수 있음이 보장된다.

• 첫째 줄에 두 정수 $X$와 $Y$가 공백으로 구분되어 주어진다.
• 다음 $Y$개의 줄에는 각각 공백 없이 정확히 $X$개의 문자가 주어지며, 지도의 맨 위 행부터 맨 아래 행까지 한 줄에 한 행씩 나타낸다. 각 문자는 .(빈 칸), *(장애물), K(소의 출발 칸), H(건초 더미) 중 하나이다. K와 H는 각각 정확히 하나씩 존재한다.

• 소가 건초 더미에 도달하기 위한 최소 점프 횟수를 정수 하나로 출력한다. 건초 더미에는 항상 도달할 수 있다.