KPvK 엔드게임

문제

《체스》는 $8 \times 8$ 격자 모양의 체스판 위에서 각자의 기물을 이용해 상대를 체크메이트시키는 것이 목적인 2인 제로섬 유한 확정 완전 정보 게임입니다. 각 플레이어는 흰색 측과 검은색 측이 되어 자기 색의 말을 각각 번갈아가면서 한 번씩 움직이게 되고, 상대의 킹을 체크메이트시키면 이기는 게임입니다.

기물의 움직임에 대한 공통적인 규칙은 다음과 같습니다.

한 턴에는 정확히 한 개의 말을 움직여야 합니다.
말을 체스판 밖으로 움직일 수는 없습니다.
말을 같은 색의 기물이 있는 칸으로 움직일 수 없습니다.
다른 색의 기물이 있는 칸으로 말을 움직이게 된 경우, 기존에 있던 말은 없어지고 새로운 말이 해당 위치에 있게 됩니다. 이를 기물을 잡는다고 합니다.

1, 4번 규칙에는 캐슬링과 앙 파상이라는 예외가 있지만, 이 문제에서는 등장하지 않습니다.

체스의 기물은 총 $6$ 종류가 있으며, 움직이는 법은 같습니다.

나이트: 상하좌우 중 한 방향을 골라 두 칸 앞으로 간 후, 왼쪽 혹은 오른쪽으로 $90$ 도 회전한 후 한 칸 앞으로 갑니다. 가운데 지나가는 칸에 기물이 있더라도 이동할 수 있습니다.
비숍: $45$ 도 대각선 네 방향중 하나로 원하는 만큼 이동할 수 있습니다. 즉, 가로와 세로로 동일한 칸 수만큼 이동할 수 있습니다. 단, 이동 전후 위치 사이에 다른 기물이 있으면 이동할 수 없습니다.
룩: 상하좌우 중 한 방향을 골라 원하는 만큼 이동할 수 있습니다. 단, 이동 전후 위치 사이에 다른 기물이 있으면 이동할 수 없습니다.
퀸: 비숍과 룩이 이동할 수 있는 곳 전부를 이동할 수 있습니다.
킹: 꼭짓점이나 변이 맞닿는 $8$ 칸 중 한 칸으로 움직일 수 있습니다.
폰: 기본적으로는 한 칸 위로 움직일 수 있습니다. 추가로 다음과 같은 규칙이 존재합니다.
- 한 칸 위에 기물이 있으면 그 칸으로 움직일 수 없습니다.
- 한 칸 대각선 위(바로 위 칸과 인접한 왼쪽 혹은 오른쪽 칸)에 다른 색의 기물이 있는 경우 해당 칸으로 움직일 수 있습니다.
- 현재 있는 칸이 아래에서 두 번째 칸인 경우, 위 두 칸 모두에 다른 기물이 없다면 두 칸 움직일 수 있습니다. (한 칸을 움직이는 것도 가능합니다.)
- 이동 후에 있는 칸이 가장 위 칸인 경우, 같은 색의 나이트, 비숍, 룩 혹은 퀸 중 하나로 기물을 바꿔야 합니다.

이 게임에서 가장 중요한 개념 중 하나는 체크 상태입니다. 어떤 색의 킹이 체크 상태에 있다는 것은 다른 색의 기물이 한 번의 움직임으로 킹이 있는 위치로 갈 수 있다는 것을 말합니다. 기물의 움직임이 끝난 후, 자신의 킹이 체크 상태이면 안 됩니다. 즉, 자신의 킹이 체크 상태에 놓이는 것을 피해야 합니다.

상대의 킹이 체크 상태이고 상대가 다음 턴에 어떤 수를 두더라도 체크 상태를 피할 수 없는 경우 상대의 킹이 체크메이트되었다고 하며, 이 경우 게임에서 승리합니다. 단, 상대의 킹이 체크 상태가 아니면서 상대가 다음 턴에 어떤 수를 두더라도 체크 상태를 피할 수 없는 경우는 스테일메이트가 되고, 게임이 비기게 됩니다.

체크메이트와 스테일메이트 이외에 게임이 종료되는 경우는 다음과 같으며, 이 경우들로 인해 게임이 종료되는 경우에는 무승부로 처리됩니다.

$50$ 수 반복: 폰의 움직임 혹은 기물을 잡는 경우가 양쪽 모두 연속한 $50$ 수 (총 $100$ 번의 움직임) 동안 없는 경우입니다.
승리할 수 없는 상태: 어떤 수를 사용하더라도 한쪽 킹이 체크메이트 상태에 놓일 수 없는 경우입니다.
$3$ 회 동형 반복: 같은 게임 상태가 $3$ 번 이상 등장한 경우입니다.

체스는 원래 각자 $16$ 개의 말을 가지고 시작하지만, 체스에서는 엔드게임이라고 불리는 단계가 매우 중요합니다. 이 단계는 기물이 별로 남지 않았을 때를 의미하고, 치밀한 수 계산을 해야 승리할 수 있습니다. 지금 상황은 체스판 위에 흰색 킹과 폰이 각각 하나씩 있고, 검은색 기물은 킹만 하나 있는 상태입니다. 양측이 최선을 다할 때, 흰색 측이 승리할 수 있을지 혹은 무승부가 될지, 승리한다면 몇 수 이내로 승리할 수 있을지 계산하는 프로그램을 만들어봅시다. 최선을 다한다는 것은 어떤 측이 이길 수 있다면 최대한 적은 수로 이기려고 하며, 이길 수 없지만 비길 수 있다면 비기려고 하며, 질 수밖에 없는 경우는 최대한 많은 수를 두려고 함을 의미합니다.

입력

입력은 $T$ 개의 테스트 케이스로 이루어집니다. 입력의 첫 줄에는 테스트 케이스의 개수 $T$ 가 주어집니다. $(1 \le T \le 200\\,000)$

각 테스트 케이스는 $8$ 개의 줄로 이루어져있습니다. 테스트 케이스의 첫 $8$ 개의 각 줄에는 길이가 $8$ 인 문자열이 주어집니다. $i$ 번째 줄의 $j$ 번째 문자는 위에서 $i$ 번째, 왼쪽에서 $j$ 번째 칸에 대한 정보를 나타냅니다.

.: 현재 칸이 비어있다는 것을 나타냅니다.
K: 현재 칸에 흰색 킹이 있다는 것을 나타냅니다,
P: 현재 칸에 흰색 폰이 있다는 것을 나타냅니다.
k: 현재 칸에 검은색 킹이 있다는 것을 의미합니다.

이후 마지막 줄에는 W 혹은 B 문자가 주어집니다. W 문자는 현재 차례가 흰색 차례, B 문자는 현재 차례가 검은색 차례라는 것을 의미합니다.

한 테스트 케이스에는 K, P, k 문자가 정확히 하나씩 등장합니다. 주어지는 체스판은 게임이 진행 중이며 올바른 상태입니다. 이는, 폰이 가장 위 혹은 아래 행에 있지 않으며, 현재 차례의 상대편 킹이 체크 상태가 아니고 현재 차례에 (본인의 킹을 체크시키지 않는) 가능한 움직임이 존재한다는 것을 의미합니다.

출력

각 테스트 케이스마다 한 줄에 하나씩 정수 하나를 출력합니다. 서로가 최적으로 플레이했을 때, 검은색 킹을 체크메이트시킬 수 있다면, 필요한 흰색 기물 이동 횟수를 출력합니다. 체크메이트시킬 수 없고 무승부로 끝난다면 $0$ 을 출력합니다.