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