폰의 각성

$N \times N$ 체스판에서 벌어진 전쟁에서 준웅나라는 상대 나라의 압도적인 병력에 밀려 폰 병사인 선우 한 명만 남았다. 절체절명의 위기 속에서 홀로 남은 폰선우가 각성했다! 각성한 폰선우는 한 턴에 다음 과정을 수행한다.

1. 처음에 폰선우는 가로, 세로, 대각선 8방향으로 한 칸 움직일 수 있다. 한 칸 움직여 킹의 위치로 이동했다면 턴을 종료한다.
2. 폰선우가 도달할 수 있는 칸 중에서 상대 말이 있는 칸을 하나 고른다. 상대 말이 있는 칸이 하나도 없다면 고를 수 없고, 폰선우의 턴은 종료된다.
3. 폰선우는 고른 칸으로 이동한다. 그 칸에 있던 말은 능력을 빼앗겨 더 이상 움직일 수 없는 돌이 되고, 폰선우는 빼앗은 이동 방법으로 현재 이동 방법을 대체한다. 이동한 위치가 킹의 위치라면 턴을 종료한다. 그렇지 않다면 현재 위치에서 2번 과정을 반복한다.

폰선우는 이 각성 능력을 써서 상대 킹을 잡으러 가야 한다. 상대의 말은 다음과 같다.

• 퀸: 가로, 세로, 대각선 8방향으로 거리 제한 없이 움직인다.

• 룩: 가로, 세로 4방향으로 거리 제한 없이 움직인다.

• 비숍: 대각선 4방향으로 거리 제한 없이 움직인다.

• 나이트: 가로, 세로 4방향 중 한 방향으로 한 칸 가고, 그 방향의 양옆 대각선 방향 중 한 방향으로 한 칸 간다. 다른 말을 뛰어넘을 수 있다. 진행 경로 중간에 장애물이 있어도 체스판을 벗어나지 않는 한 반드시 초록색 칸으로 이동할 수 있다.

대각 이동도 한 칸으로 센다. 예를 들어 나이트는 상하좌우 중 1칸, 대각 1칸을 움직이므로 한 번에 항상 2칸씩 이동한다.

폰선우는 능력을 한 번 빼앗아 돌이 된 말에게서 다시 능력을 빼앗을 수 없다. 현재 능력이 나이트인 경우를 제외하면 폰선우는 다른 말이나 돌을 뛰어넘을 수 없다.

폰선우가 한 턴 만에 상대 킹을 잡을 수 있다면, 최소 칸 수를 이동하여 킹을 잡도록 도와주자. 킹을 잡을 수만 있다면 체스판에 다른 말이 남아 있어도 상관없다.

첫째 줄에 $N$($2 \le N \le 1\,000$)이 주어진다.

둘째 줄부터 $N$줄에 걸쳐 줄마다 $N$개의 문자가 공백으로 구분되어 주어진다. 이때 0은 빈칸, Q는 퀸, R는 룩, B는 비숍, N은 나이트, K는 킹, P는 폰선우를 뜻한다.

킹과 폰선우는 각각 반드시 한 개씩 존재한다. 퀸은 최대 1개만 존재한다.

폰선우가 한 턴 만에 상대 킹을 잡을 수 있다면, 킹을 잡기까지 이동한 최소 칸 수를 첫째 줄에 출력한다. 한 턴 만에 잡을 수 없다면 -1을 출력한다.