题目描述

$N * N (1 \le N \le 100)$ 方格中，'x' 表示不能行走的格子，'.' 表示可以行走的格子。卡门很胖，故而不好转弯。现在要从 $A$ 点走到 $B$ 点，请问最少要转 $90$ 度弯几次？

输入格式

第一行一个整数 $N$，下面N行，每行 $N$ 个字符，只出现字符：'.'，'x'，'A'，'B'，表示上面所说的矩阵格子，每个字符后有一个空格。

输出格式

一个整数：最少转弯次数。如果不能到达，输出 $-1$。

样例 #1

样例输入 #1

3
. x A
. . .
B x .

样例输出 #1

2

提示

【注释】

只可以上下左右四个方向行走，并且不能走出这些格子之外。开始和结束时的方向可以任意。