暂无测试数据。

wy 最近在玩一款名为《传送门》的单机游戏。

游戏中玩家可以控制一个人物在地图上移动，而每轮游戏开始时，地图上会随机出现一些传送门。

游戏地图是一个大小为 $n * m$ 的矩阵，玩家出生在 $(1,1)$，而每次游戏需要到达终点 $(n,m)$ 才能获得胜利。

在游戏中原本就存在一些墙，用#表示，而能够行走的空地则用.表示，每秒钟玩家可以选择上下左右任意一个方向进行一次移动（不能呆在原地不动）。

而在空地上会随机出现一些传送门，传送门用大写字母表示，例如 $A,B,C...$，地图上可能出现多个传送门，但是每个传送门一定是成对出现的。

即如果存在传送门 $A$，则地图上有且必然仅有两个传送门 $A$，且玩家无法选择是否传送，只要进入传送门就必然会被传送到另一个传送门处。

设两个传送门 $A$ 分别为 $A_1$ 和 $A_2$。

当玩家踏入 $A_1$ 的瞬间就会被传送到 $A_2$ 处（传送过程不消耗时间，且传送门永久存在不会消失）。

但此时为了防止时空紊乱，$A_2$ 传送门会暂时失效 $1$ 秒钟。

例如如下地图

.#.
A#A
.#.

当玩家进入某个传送门时，会立刻传送到另一个传送门处，例如上图，当玩家移动到 $(2,1)$ 时会立刻传送到 $(2,3)$，此时 $(2,3)$ 的传送门会失效 $1$ 秒钟。

若玩家想返回 $(2,1)$ 则需要先进行一次移动到达 $(1,3)$ 或 $(3,3)$，再返回 $(2,3)$ 才会被传送回 $(2,1)$。

现在 wy 已经开始了一轮游戏，她想知道最少花费多少时间就能获得胜利？

输入格式

输入第一行包含两个正整数 $n,m$ 含义如题。

接下来 $n$ 行，每行 $m$ 个字符，其中#表示墙，.表示空地，大写字母表示传送门。

输入保证同一个大写字母有且只会出现两次。

输出格式

输出只有一行，该行只有一个正整数，表示 wy 获胜最少需要花费的时间。

若无法获胜则输出Game Over.。

数据范围

对于 $60\%$ 的数据，$N,M \leq 20$

对于 $100\%$ 的数据，$N,M \leq 100$

3 3
.#.
A#A
.#.

2