打败了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，0]或[0，N]或[N,0]的位置，然后走一步到原点，所以原点算作一步）。

第一行一个数N，表示迷宫的大小（N*N）（0<=N<=1400）

以下N行，每行N个字符，表示迷宫的示意图。字符要么是字母ABC，要么是障碍。A表示时空之门，B表示海洋之门，C表示天堂之门，障碍用*表示。

为Mini从原点处走到公主处的最短路径（最短路径不一定消耗步数最少）所消耗的步数（若有多条最短路径则输出消耗步数最少的那个）。无解输出“No answer”（引号不输出）