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