Problem Background

Du Naisu and F91 are good friends.

Problem Description

They often play a game together, not StarCraft, but chess.

Du Naisu thinks F91 is a chicken. He sets up a formation on an n×n chessboard using black rooks, knights, bishops, queens, kings, and pawns.

However, F91 thinks Du Naisu is a chicken. He challenges Du Naisu: he will control a white knight, avoiding the attack range of any black piece (F91 can move continuously, while Du Naisu's pieces remain stationary unless the white knight enters their attack range), and kill Du Naisu's king (i.e., reach the position of the black king).

Please tell F91 the minimum number of steps required to accomplish this feat.

Notes:

1. When F91's white knight moves onto a square occupied by Du Naisu's piece, it will kill (capture) that piece. This piece will no longer threaten F91's white knight.

2. If the white knight starts within the attack range of a black piece, it is immediately killed, and F91 immediately loses.

3. Even if the white knight enters the attack range of other pieces while attacking the king (i.e., other pieces "guard" the king's square), F91 still wins.

Attack Ranges:

• Rook: All positions horizontally and vertically until blocked by another piece.
  cpp ..#.. ..#.. ##C## ..#.. ..#..

• Knight: Positions two squares in one direction and one square in a perpendicular direction (up to 8 positions, resembling the shape of the Chinese character "日").
  cpp .#.#. #...# ..K.. #...# .#.#.

• Bishop: All positions diagonally (45°) until blocked by another piece.
  cpp #...# .#.#. ..B.. .#.#. #...#

• Queen: Combination of rook and bishop (can attack horizontally/vertically and diagonally at 45° angles until blocked by another piece).
  cpp #.#.# .###. ##Q## .###. #.#.#

• King: The 8 adjacent squares.
  cpp ..... .###. .#X#. .###. .....

• Pawn: The squares diagonally forward (up to 2 positions).
  cpp ..... ..... ..P.. .#.#. .....

Where the letters represent the types of pieces, as per the input format.

'#' indicates the attack range.

Input Format

The input contains multiple sets of data.

For each set of data, the first line contains an integer n representing the size of the chessboard.

The next n lines, each containing a string of length n, describe the layout of the chessboard.

Where:

• '.' indicates an empty square.
• 'O' indicates the white knight.
• 'C' indicates the black rook.
• 'K' indicates the black knight.
• 'B' indicates the black bishop.
• 'Q' indicates the black queen.
• 'X' indicates the black king.
• 'P' indicates the black pawn.

Output Format

For each test case, output an integer on a single line, representing the minimum number of steps F91 needs.

If F91 cannot kill the black king no matter what, output -1.

Sample Input and Output

Sample Input #1

8
...X....
........
........
........
........
........
........
......O.

Sample Output #1

4

Sample Input #2

8
......X.
........
.O......
...P.Q.C
.....B..
........
...K....
........

Sample Output #2

7

Notes

The input contains at most 5 sets of data.

• For 20% of the data, Du Naisu only has the king. n <= 8.
• For 30% of the data, Du Naisu only has the king and knight. n <= 8.
• For 60% of the data, Du Naisu only has the king, knight, and queen. n <= 50.
• For 100% of the data, Du Naisu can have the full set of 16 pieces (2 rooks, 2 knights, 2 bishops, 1 queen, 1 king, 8 pawns). n <= 50.

Tip:

The time limit may be tighter than expected, so pay attention to implementation details to ensure performance.

Sample 2 Explanation:

One possible solution is:

......X.
.3..6...
.O5.....
4.2P.Q.C
1....B..
........
...K....
........

见题面 Input 部分

见题面 Output 部分