题目描述

$\red{Bessie }$再次被困在 $\red{Farmer John }$谷仓的错误一侧，由于她的视力很差，她需要你的帮助才能穿过谷仓。

谷仓由 $\red{N×}$$\red{N }$方格 $\red{(2≤}$$\red{N≤}$$\red{20) }$组成，有些是空的，有些包含无法通过的干草堆。

$\red{Bessie }$从左下角单元格$\red{（ 1,1）}$开始，想要移动到右上角单元格 $\red{（N,N）}$。

您可以通过告诉她一系列指令来引导她，每个指令要么是"向前"、"左转 $\red{90 }$度"或"右转 $\red{90 }$度"。你想发出最短的指令序列，引导她到达目的地。如果您指示 $\red{Bessie }$离开网格（即进入谷仓墙）或进入干草堆，她将不会移动并跳到您序列中的下一个命令。

不幸的是，$\red{Bessie }$不知道她一开始是朝上（朝向单元格$\red{1,2}$）还是朝右（朝向单元格 $\red{2,1}$）。

无论哪种情况是正确的，您都需要给出最短的方向序列，以引导她到达目标。一旦她达到目标，她将忽略进一步的命令

输入格式

输入的第一行包含 $\red{N}$。

后面的每一行 $\red{N }$都包含正好 $\red{N }$个字符的字符串，代表谷仓。

最后一行的第一个字符是单元格 $\red{（1,1）}$。

第一行的最后一个字符是单元格 $\red{(N，}$$\red{N）}$。

每个字符要么是一个 $\red{H }$来表示一个干草堆，要么是一个 $\red{E }$来表示一个空方块。 保证单元格$\red{（1,1）}$ 和 $\red{(N，}$$\red{N）}$为空，并且保证从单元格$\red{（1,1）}$ 到单元格$\red{(N，}$$\red{N）}$有一条空方格路径。

输出格式

在一行输出中，输出将引导贝西到达目标的最短方向序列的长度，无论她是开始朝上还是向右。

样例

输入样例

3
EHE
EEE
EEE

输出样例

9

提示

在本例中，指令"向前、向右、向前、向前、向左、向前、向左、向前、向前"将引导贝西到达目的地，而不管她的起始方向如何。