Bessie 又困在 Farmer John 牛棚的錯誤一側。她視力很差，需要你幫忙穿過牛棚。

牛棚為 $N \times N$ 個正方形格子的網格 ($2 \leq N \leq 20$)，有的為空，有的有不可通過的乾草捆。Bessie 從左下角（格子 $(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