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