회전

흥미진진한 Join-K 게임에서는 빨간색 말과 파란색 말을 $N \times N$ 표에 떨어뜨린다. 표는 수직으로 세워져 있으므로 말은 해당 열에서 가장 아래에 있는 빈칸까지 떨어진다. 예를 들어, 다음 두 배치를 살펴보자.

이 그림에서 각 '.'은 빈칸을, 각 'R'은 빨간색 말이 놓인 칸을, 각 'B'는 파란색 말이 놓인 칸을 나타낸다. 왼쪽 배치는 올바르지만 오른쪽 배치는 올바르지 않다. 세 번째 열에서 화살표로 표시된 말 하나가 그 아래의 빈칸까지 떨어지지 않았기 때문이다.

플레이어는 가로, 세로 또는 대각선 방향 중 하나로 자신의 색 말 적어도 K개를 일렬로 놓을 수 있으면 승리한다. 가능한 네 가지 방향은 아래와 같다.

문제 설명 앞부분의 "Legal Position" 그림에서는 두 플레이어 모두 말 두 개를 일렬로 놓았지만, 세 개를 놓지는 못했다.

알고 보니 지금 당신은 매우 흥미진진한 Join-K 게임을 하고 있으며, 승리를 확실히 하기 위한 교묘한 계획이 있다! 상대가 보고 있지 않을 때 보드를 시계 방향으로 90도 회전하여 옆으로 눕힐 것이다. 그러면 중력으로 인해 말들이 아래와 같이 새로운 위치로 떨어진다.

안타깝게도 상대가 알아차리기 전에 보드를 회전할 수 있는 기회는 한 번뿐이다.

이제 남은 일은 행동에 나설 적절한 시점을 고르는 것이다. 보드의 배치가 주어질 때, 보드를 시계 방향으로 회전하고 새로운 방향으로 중력이 작용한 뒤 어느 플레이어가 K개의 말을 일렬로 놓게 되는지, 또는 두 플레이어 모두 그렇게 되는지를 판별해야 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 3 ≤ K ≤ N.

작은 데이터 세트 (테스트 세트 1 - 공개)

3 ≤ N ≤ 7.

큰 데이터 세트 (테스트 세트 2 - 비공개)

3 ≤ N ≤ 50.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 정수 N과 K가 들어 있는 한 줄로 시작한다. 다음 N개의 줄은 각각 정확히 N개의 문자로 이루어지며, 위 그림과 같은 형식으로 보드의 초기 배치를 나타낸다.

각 테스트 케이스의 초기 배치는 Join-K 게임 도중에 나올 수 있는 올바른 배치이다. 특히 어느 플레이어도 이미 K개의 말을 일렬로 놓은 상태가 아니다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 "Red", "Blue", "Neither", "Both" 중 하나이다. 여기서 y는 보드를 회전한 뒤 어느 플레이어가 K개의 말을 일렬로 놓게 되는지, 또는 어느 플레이어들이 그렇게 되는지를 나타낸다.

• 보드는 한 번만 회전할 수 있다.

• 중력은 보드가 완전히 회전한 뒤에만 작용한다고 가정한다.

• 중력의 작용이 끝난 뒤에만 승자를 확인한다.