판 돌리기

Join-K는 빨간 말과 파란 말을 $N \times N$ 판에 떨어뜨리는 게임이다. 판이 세워져 있어서 말은 떨어뜨린 열에서 가장 아래의 빈 칸까지 내려간다. 아래 그림에서 '.'은 빈 칸, 'R'은 빨간 말이 놓인 칸, 'B'는 파란 말이 놓인 칸이다.

다음은 올바른 배치이다.

.......
.......
.......
....R..
...RB..
..BRB..
.RBBR..

다음은 올바르지 않은 배치이다.

.......
.......
.......
.......
..BR...
...R...
.RBBR..

세 번째 열의 'B' 아래에 빈 칸이 있어서, 말을 어떤 순서로 떨어뜨려도 이 배치는 나오지 않는다.

자기 색 말을 세로, 가로, 두 대각선 중 한 방향으로 $K$개 이상 연속해서 놓은 사람이 이긴다. 네 방향을 $K = 4$로 그리면 다음과 같다.

R...   RRRR   R...   ...R
R...   ....   .R..   ..R.
R...   ....   ..R.   .R..
R...   ....   ...R   R...

위의 올바른 배치에서는 두 사람 모두 두 개까지만 연속해서 놓았고, 세 개를 놓은 사람은 없다.

지금 Join-K를 한 판 두는 중이고, 상대가 보지 않는 사이에 판 전체를 시계 방향으로 90도 돌리려고 한다. 판을 돌리면 중력이 새 방향으로 모든 말을 아래로 끌어내린다.

처음 배치:

.......
.......
.......
...R...
...RB..
..BRB..
.RBBR..

시계 방향으로 90도 돌린 직후:

.......
R......
BB.....
BRRR...
RBB....
.......
.......

중력이 다 작용한 뒤:

.......
.......
.......
R......
BB.....
BRR....
RBBR...

판은 한 번만 돌릴 수 있다. 중력은 판을 끝까지 돌린 뒤에만 작용하고, 승자는 중력이 다 작용한 뒤에만 확인한다.

처음 배치가 주어지면, 판을 시계 방향으로 돌리고 말이 다 내려앉았을 때 $K$개를 연속으로 놓은 사람이 누구인지 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 두 정수 $N$과 $K$가 주어진다. 다음 $N$개 줄에는 각각 정확히 $N$개의 문자가 주어지며, 위와 같은 형식으로 처음 배치를 나타낸다.

처음 배치는 Join-K 게임에서 나올 수 있는 올바른 배치이고, 아직 어느 쪽도 $K$개를 연속으로 놓지 않았다.

• $1 \le T \le 100$
• $3 \le N \le 7$
• $3 \le K \le N$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 Red, Blue, Neither, Both 중 하나이다. y는 판을 돌리고 말이 다 내려앉은 뒤에 $K$개를 연속으로 놓은 사람을 나타낸다.