考虑一个 N x N (1 <= N <= 100) 的正方形牧场，有些方格是奶牛不能踏上的，标记为'x'。例如下图：

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

贝茜恰好在点A处，想去B处的盐块。奶牛讨厌转弯，仅在必要时转弯。请计算从A到B最少的转弯次数。开始时贝茜可以面向任意方向，题目保证存在可行路径。

输入描述

第1行：一个整数 N 第2~N+1行：每行有 N 个字符（'.'、'x'、'A'、'B'），表示每个点的状态。

输出描述

输出1个整数，代表最少的转弯次数。

输入样例1

3
.xA
...
Bx.

输出样例1

2