题目描述

有一块 $N \times N(1 \le N \le 100)$ 的牧场，被划分成 $N^2$ 个 $1 \times 1$ 的小方格。有的方格堆着杂物，奶牛走不进去，用 $\texttt x$ 标出；其余方格畅通，用 $\texttt .$ 标出。

奶牛 Daisy 正站在 $A$ 格，她想到 $B$ 格去舔放在那里的盐砖。奶牛天性笨拙，最烦的就是转弯，而且她只能沿着平行于方格边的方向一步一步挪动。

给定整块牧场的情况，请你求出从 $A$ 走到 $B$ 的所有路线中，最少需要转多少次 $90^{\circ}$ 的弯。出发时朝向和到达时朝向都可以任意。

如果 Daisy 根本走不到 $B$ 格，输出 -1。

输入格式

第一行一个正整数 $N$，表示牧场的边长。

接下来 $N$ 行，每行一个长度为 $N$ 的字符串，每个字符是 $\{\texttt{x},\texttt{.},\texttt{A},\texttt{B} \}$ 之一，描述对应方格的状况。

输出格式

一行一个整数，表示 Daisy 至少要转的弯数。

样例

3
. x A
. . .
B x .

2

提示

【样例 $1$ 解释】

Daisy 至少要转两次弯：比如她先面朝南走一步，转身朝西走两步，再转身朝南走一步，就走进了 $B$ 格。（按“上北下南左西右东”理解）