Awakening of the Pawn

On an $N \times N$ chessboard, the army of Junung was overwhelmed by the enemy, and only one pawn, Seonwoo, is left. Facing a desperate crisis, the lone pawn Seonwoo awakens! The awakened Seonwoo performs the following steps in one turn.

1. At first, Seonwoo can move one square in any of the 8 directions: horizontally, vertically, or diagonally. If the move lands on the enemy king, the turn ends.
2. Seonwoo selects one square with an enemy piece among the squares it can reach. If no square has an enemy piece, nothing can be selected and the turn ends.
3. Seonwoo moves to the selected square. The piece on that square loses its ability and becomes a stone that can no longer move. Seonwoo replaces its current movement with the ability it took. If the square it moved to is the enemy king's square, the turn ends. Otherwise, Seonwoo repeats step 2 from its current position.

With these abilities, Seonwoo must go after the enemy king. The enemy pieces are as follows.

• Queen: moves any distance in 8 directions, horizontally, vertically, and diagonally.

• Rook: moves any distance in 4 directions, horizontally and vertically.

• Bishop: moves any distance in 4 diagonal directions.

• Knight: moves one square in one of the 4 horizontal or vertical directions, then one square diagonally in one of the two directions beside it. It can jump over other pieces. In other words, even if there are obstacles on the path, it can always reach a green square as long as it stays on the board.

A diagonal move also counts as one square. For example, a knight moves one square horizontally or vertically and one square diagonally, so it always moves 2 squares in total.

Once Seonwoo takes the ability of a piece, it cannot take the ability of that stone again. Unless its current ability is a knight, Seonwoo cannot jump over other pieces or stones.

If Seonwoo can capture the enemy king in one turn, help it capture the king by moving the minimum number of squares. Other pieces may remain on the board as long as the king can be captured.

The first line contains $N$ ($2 \le N \le 1\,000$).

From the second line on, $N$ lines follow, each with $N$ characters separated by spaces. Here, 0 is an empty square, Q is a queen, R is a rook, B is a bishop, N is a knight, K is the king, and P is Seonwoo.

There is exactly one king and exactly one Seonwoo. There is at most one queen.

If Seonwoo can capture the enemy king in one turn, print the minimum number of squares it must move to capture the king on the first line. If it cannot capture the king in one turn, print -1.