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