가난한 왕

체스판 위에 흰색 말 두 개와 검은색 킹 하나가 있다. 흰색 말은 각각 룩, 비숍, 퀸 중 하나이다. 지금은 흰색 차례이다. 당신은 흰색을 맡아 검은색 킹을 가능한 한 적은 수로 체크메이트해야 한다. 검은색이 게임을 최대한 오래 끌려고 최선의 전략을 쓴다고 가정할 때, 흰색이 체크메이트하는 데 필요한 최소 이동 횟수를 구하는 프로그램을 작성하라.

이 문제에서 사용하는 체스 규칙:

1. 보드에 흰색 킹이 없으므로 이 배치는 실제 체스에서 합법적이지 않다. 그 밖에는 게임이 일반 체스 규칙에 따라 진행된다.
2. 체스판은 $8 \times 8$ 칸이다. 열은 a부터 h, 행은 1부터 8로 표시한다.
3. 양측은 번갈아 자기 색 말을 하나씩 움직인다. 이 문제에서는 흰색이 둔 수만 센다.
4. 룩은 가로나 세로로 빈 칸을 지나 몇 칸이든 움직인다. 같은 색 말을 뛰어넘거나 같은 색 말이 있는 칸에 설 수 없다.
5. 비숍은 대각선으로 빈 칸을 지나 몇 칸이든 움직인다. 같은 색 말을 뛰어넘거나 같은 색 말이 있는 칸에 설 수 없다.
6. 퀸은 가로, 세로, 대각선으로 빈 칸을 지나 몇 칸이든 움직인다. 같은 색 말을 뛰어넘거나 같은 색 말이 있는 칸에 설 수 없다.
7. 체크는 다음 수에 킹을 잡겠다고 위협하는 상태이다.
8. 킹은 어느 방향으로든 한 칸씩 움직인다. 그 결과 체크를 받게 되면 그 수는 둘 수 없다. 이 조건이 성립하면 킹은 인접한 흰색 말이 있는 칸으로 들어가 말을 잡을 수 있으며, 잡힌 말은 게임에서 제외된다.
9. 체크메이트는 킹이 체크를 받고 있으면서 위협을 피할 합법적인 수가 없는 상태이다.
10. 스테일메이트는 차례인 쪽이 체크를 받지 않았는데 합법적인 수가 없는 상태이다. 체스 규칙상 스테일메이트는 무승부이며, 흰색에게는 받아들일 수 없는 결과이다.

첫 줄에는 배치의 개수가 주어진다. 개수는 최대 $1.5 \cdot 10^5$이다. 이어지는 각 줄은 배치 하나를 나타낸다. 검은색 킹의 위치를 먼저 주고, 그다음 흰색 말 두 개의 위치를 준다. 흰색 말의 위치 앞에는 말 종류를 나타내는 문자가 붙는다. R은 룩, B는 비숍, Q는 퀸이다.

두 말이 같은 칸에 있지 않고, 초기 배치에서 검은색 킹이 체크를 받고 있지 않다고 보장된다. 그 밖의 배치는 임의로 주어질 수 있다. 예를 들어 흰색 말 두 개가 모두 퀸일 수도 있다.

각 배치마다 그 배치에서 흰색이 체크메이트를 확실히 하는 데 필요한 최소 수를 한 줄에 출력한다. 목표에 도달할 수 없으면 0을 출력한다.