Considere un campo cuadrado ~(N x N)~ compuesto por cuadrados de 1 por 1. Algunos de estos cuadrados son impasables por vacas y están marcados con una ~'x'~ en este campo 5 por 5 que es desafíante para atravesar:

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

Bessie se encuentra en un campo así en una posición ~A~ y quiere moverse a una ubicación ~B~ con el propósito de lamer el bloque de sal que está allí. A las criaturas lentas y torpes como las vacas no les gusta giros, y por supuesto, pueden solo moverse paralelamente a los ejes del campo cuadrangular. Para un campo dado, determine el número mínimo de giros de noventa grados en cualquier camino de ~A~ a ~B~. El camino puede comenzar y terminar con Bessie mirando en cualquier dirección. Bessie sabe que ella puede llegar a lamer la sal.

Entrada

• Línea 1: Un solo entero: ~N~.
• Líneas 2..N+1: La línea i+1 representa la fila ~i~ del campo con ~N~ caracteres como en el ejemplo ya mostrado (esto es, ~'.'~, ~'x'~, ~'A'~, y ~'B'~); no hay espacios presentes en una línea.

Ejemplo de Entrada

3
.xA
...
Bx.

Detalles de la Entrada: La vaca necesita desplazarse de la esquina superior derecha a la esquina inferior izquierda, sin pasar por el cuadrado central de arriba ni por el cuadro central de abajo.

Salida

En una línea un solo entero, el número mínimo de giros que la vaca debe hacer para realizar el recorrido.

Ejemplo de Salida

2

Detalles de la Salida: La vaca debe hacer al menos 2 giros: Por ejemplo, la vaca puede comenzar mirando hacia el sur, moverse hacia el sur, girar a mirar al oeste, moverse hacia el oeste, moverse al oeste, luego girar para mirar al sur, y finalmente moverse hacia el sur en el cuadrado ~B~.