题目描述

你掉进了一个巨大的棋盘里面，里面只有行和列，姑且用一个平面直角的坐标系来表示。你只能像中国象棋中的马一样行走，你的起始位置用’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,D``…`这条路径用$\red 5$次去到出口（不排除其它路线也是$\red 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行： 两个数，表示棋盘的列数$\red{L(L<=150)}$和行数$\red{H(H<=150)}$。

第2..R+1行: 每行一个由$\red{L}$个字符组成的字符串，这就是地图。

输出格式

一个整数，即最小次数。

样例

输入样例

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

输出样例

5

提示

注意： 数据保证一定有解。