本题的主角 Chell 必须解决 GLaDOS 设计的一个新谜题。

Chell 处在一个大小为 $N$ 行 $M$ 列的网格房间中。每个格子可以是以下几种之一：

• 障碍格：其中有一面墙（用 # 表示）。
• Chell 的初始位置（用 C 表示）。
• Chell 必须到达的目标位置以解决谜题（用 F 表示）。
• 空地（用 . 表示）。

Chell 携带着一把所谓的传送枪，可以用它在墙上创建传送门。在每一步中，她可以执行以下操作之一：

• 向上、下、左或右移动到相邻的格子（她不能移动到有墙的格子）。此移动花费 $1$ 个单位的时间。
• 朝上、下、左或右方向的一面墙（不一定是相邻的墙）转身并射击，在墙上创建一扇传送门。传送门只会创建在被射击击中的那一侧墙面上。在任何时刻，最多只能同时存在两扇活跃的传送门。如果已经存在两扇活跃的传送门，此时再创建一扇新传送门，则最早创建的那扇传送门将会消失。不能在已有传送门的位置创建新的传送门。此操作花费的时间可以忽略不计，即花费 $0$ 个单位的时间。
• 如果她处于与墙相邻的格子，且该墙朝向她的一侧有一扇传送门，她可以步入该传送门，并从另一扇传送门所在的非障碍格子走出来。只有在存在两扇活跃的传送门时才能进行此操作，此移动花费 $1$ 个单位的时间。

Chell想知道她解决谜题（即到达标有 F 的格子）所需的最少时间。

请注意：房间的四周边界总是被墙壁包围，且字母 C 和 F 在矩阵中各仅出现一次。

输入格式

输入的第一行包含正整数 $N$ 和 $M$（$4 \le N, M \le 500$），表示房间的尺寸。

接下来的 $N$ 行，每行包含 $M$ 个字符，描述房间的布局。

输出格式

输出解决谜题所需的最少时间。如果无法解决，则输出 nemoguce（不含引号）。

子任务

对于 $50\%$ 的测试数据，满足 $4 \le N, M \le 15$。

样例

输入格式 1

4 4
####
#.F#
#C.#
####

输出格式 1

2

输入格式 2

6 8
########
#.##..F#
#C.##..#
#..#...#
#.....##
########

输出格式 2

4

输入格式 3

4 5
#####
#C#.#
###F#
#####

输出格式 3

nemoguce

说明

样例 2 解释：

该谜题可以通过 $8$ 步解决，如下图所示。

第一步，我们向左侧的墙壁转身并射击，在第 $3$ 行第 $1$ 列（坐标为 $(3,1)$）的墙壁右侧创建一扇传送门。

第二步，我们在坐标为 $(6,2)$ 的墙壁上侧创建一扇传送门。

第三步，我们步入位于 $(3,1)$ 的传送门，并从位于 $(6,2)$ 的第二扇传送门相邻的非障碍格子 $(5,2)$ 走出来。

第四步，我们向右转身，在坐标为 $(5,7)$ 的墙壁左侧创建一扇传送门。由于此时已经存在两扇传送门，位于 $(3,1)$ 的传送门消失。

第五步，我们步入位于 $(6,2)$ 的传送门，并从第二扇传送门相邻的 $(5,6)$ 处走出来。

第六步，我们在坐标为 $(1,6)$ 的墙壁下侧创建一扇新传送门，使得位于 $(6,2)$ 的传送门消失。

第七步，我们步入位于 $(5,7)$ 的传送门，并从 $(2,6)$ 处走出来。

最后，在第八步中，我们向右移动一格以结束游戏。

在第 $1$、 $2$、 $4$ 和 $6$ 步中创建传送门花费的时间为 $0$，而其余的移动每步花费 $1$ 个单位的时间，因此解决该谜题所需的总时间为 $4$ 个单位的时间。

样例 2 解释步骤图示