Bessie はまた Farmer John の牛小屋の反対側に困っています。視力が悪く、小屋を渡るための助けが必要です。

小屋は $N \times N$ の正方形マス ($2 \leq N \leq 20$) で、空か通れない干し草があります。左下の $(1,1)$ から右上の $N,N$ へ進みます。「前進」「左へ 90 度回転」「右へ 90 度回転」の最短指示列を与えます。外（小屋の壁）や干し草に進もうとすると動かず次の指示に進みます。

初期方向は上、$(1,2)$ 向きか、右、$(2,1)$ 向きか不明です。どちらでも到着する最短列をください。着いた後は以後の指示を無視します。

入力

標準入力から読み込みます。

最初の行は $N$。

続く $N$ 行は各 $N$ 文字で小屋を表します。最終行の最初が $(1,1)$、最初の行の最後が $(N,N)$ です。

H は干し草、E は空のマスです。

$(1,1)$ と $N,N$ は空で、$(1,1)$ から $N, N$ への空マスの経路が保証されます。

出力

標準出力に書き出します。

初期方向が上でも右でも到着する最短指示列の長さを一行に出力します。

入出力例

入力 1

3
EHE
EEE
EEE

出力 1

9

注記

例では「前進、右、前進、前進、左、前進、左、前進、前進」でどちらの方向からでも到着します。

問題作成：Brian Dean