题目描述

打败了 DIABLO，Mini 进入了迷宫。这是个奇怪的迷宫，迷宫的每一个地点要么有一个用来传送的门，要么是障碍。Mini 现在站在迷宫的原点处，但是眼看远在 $(N,N)$ 的公主就要被转移，Mini 心情焦急万分，为了能最快地到达公主处救出公主，Mini 希望能走一条最快的路径。注意，Mini 可以把迷宫的 $(1,1)$ 或 $(1,N)$ 或 $(N,1)$ 处当作原点。

迷宫里，某些地点会有门，将门激活，Mini 就会被传送到某个地点，当然，魔王 Bill 只创造了三种门，所以迷宫里最多有就只有三种门，而且在这个迷宫中要到达下一个点必须通过门。。（什么逻辑 TUT。。）

在迷宫中，可能会遇到的三种门分别如下：

• 时空之门，Mini 可以往上下左右四个方向中的任意一个方向传送一格；
• 海洋之门，Mini 可以往上下左右四个方向中的任意一个方向传送两格；
• 天堂之门，Mini 需要停留一步，聚气，然后可以往左上左下右上右下四个方向中的任意一个方向传送一格。

当然，使用每一个门都算作一步。

当然还有障碍，如果有障碍，那么这个点没有门且这个点不能被传送到。

但是，魔王 Bill 有可能创造出了一个完全无法到达 $(N,N)$ 的迷宫，所以，当从三个原点出发都无法到达 $(N,N)$ 时，请输出 No answer。注意，原点算作一步（Mini 一开始站在 $(1,1)$ 或 $(1,N)$ 或 $(N,1)$ 的位置，然后走一步到原点，所以原点算作一步）。

输入格式

第一行一个数 $N$，表示迷宫的大小 $N\times N$。

以下 $N$ 行，每行 $N$ 个字符，表示迷宫的示意图。字符要么是字母 ABC，要么是障碍。

A 表示时空之门，B 表示海洋之门，C 表示天堂之门，障碍用 $*$ 表示。

输出格式

输出为 Mini 从原点处走到公主处的最快路径长度。无解输出 No answer。

3
A*C
*AC
ACA

No answer

3
AAA
CAA
AAA

3

提示

对于 $100\%$ 的数据，$0\le N\le 1200$。