엔드게임

체스판에는 흰색 킹, 검은색 킹, 흰색 룩만 남아 있다. 지금은 흰색의 차례다. 상대가 최선을 다해 두며 패배를 최대한 늦춘다고 가정할 때, 흰색이 체크메이트를 부르는 데 필요한 최소 수를 구하라.

체스 규칙은 힌트 섹션에 정리해 두었다. 이미 알고 있다면 넘어가도 된다. 이 문제를 푸는 데 여러분의 체스 실력은 도움이 되지 않는다.

첫 줄에 테스트 케이스의 수 $z$ ($1 \leq z \leq 10$)가 주어진다. 각 테스트 케이스는 체스판을 나타내는 8줄로 주어진다. 각 줄은 정확히 8글자이며, .은 빈 칸, W는 흰색 킹, B는 검은색 킹, R은 흰색 룩이다. 말은 종류마다 하나씩만 있다. 시작 위치는 유효하다. 두 킹은 인접하지 않고, 검은색 킹은 공격받고 있지 않다. 각 테스트 케이스 뒤에는 빈 줄이 있다.

각 테스트 케이스마다 흰색이 체크메이트를 부르는 데 필요한 최대 수를 한 줄에 정수로 출력한다. 흰색의 수만 센다.

체스 규칙:

• 두 플레이어는 번갈아 가며 한 턴에 말 하나를 움직인다.
• 차례를 넘길 수 없다. 매 턴마다 합법적인 수를 반드시 두어야 한다.
• 킹은 가로, 세로, 대각선 중 어느 방향으로든 한 칸 움직인다.
• 룩은 같은 행이나 열을 따라 원하는 만큼 움직이지만, 다른 말을 뛰어넘을 수 없다.
• 상대 말이 그 칸으로 이동할 수 있으면 킹은 공격받는 상태다.
• 자신의 킹을 공격받는 상태에 놓거나 그대로 두는 수는 둘 수 없다. 특히 킹을 상대 킹과 인접한 칸으로 옮길 수 없다.
• 흰색 킹이 룩과 인접하지 않으면 검은색 킹은 흰색 룩이 있는 칸으로 이동할 수 있다. 이때 룩이 잡히고 게임은 무승부로 끝난다.
• 검은색에게 합법적인 수가 없으면 게임이 끝난다. 검은색 킹이 공격받는 상태면 체크메이트(흰색 승리), 아니면 스테일메이트(무승부)다.
• 위에서 설명한 상황(킹과 룩 대 킹)에서는 체크메이트가 항상 50수 미만에 가능하다고 알려져 있다.