题目描述

考虑一个 $\red{N \times N (1 <= N <= 100)}$的有$\red{1}$个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的，它们被标记为了'$\red{x}$'。例如下图：

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

贝茜发现自己恰好在点$\red{A}$处，她想去$\red{B}$处的盐块舔盐。缓慢而且笨拙的动物，比如奶牛，十分讨厌转弯。尽管如此，当然在必要的时候她们还是会转弯的。

对于一个给定的牧场，请你计算从$\red{A}$到$\red{B}$最少的转弯次数。开始的时候，贝茜可以使面对任意一个方向。贝茜知道她一定可以到达。

输入格式

第 $\red{1}$行: 一个整数 $\red{N }$行 第$\red{2..N + 1}$行: 第 $\red{i+1 }$行有 $\red{N }$个字符 $\red{(}$'$\red{.}$', '$\red{x}$', '$\red{A}$', '$\red{B}$'$\red{)，}$表示每个点的状态。

输出格式

第 $\red{1}$行: 一个整数，最少的转弯次数。

样例

输入样例

3
.xA
...
Bx.

输出样例

2