题目描述

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

. . B x . 
. x x A . 
. . . x . 
. x . . . 
. . x . .

输入格式

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

输出格式

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

3
. x A
. . .
B x .

2

提示

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

数据范围及约定

对于全部数据，保证 $2\le N\le 100$。