Rotate the Board

In the game Join-K, red and blue pieces drop into an $N \times N$ board. The board stands upright, so a piece falls to the lowest empty cell of the column it is dropped into. In the pictures below, '.' is an empty cell, 'R' is a cell holding a red piece, and 'B' is a cell holding a blue piece.

This position is legal.

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

This position is not.

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

The 'B' in the third column has an empty cell under it, so no sequence of drops produces that board.

A player wins by lining up at least $K$ pieces of their own color vertically, horizontally, or along either diagonal. The four orientations, drawn with $K = 4$, are:

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

In the legal position above, both players have two pieces in a row and neither has three.

You are in the middle of a game of Join-K, and while your opponent looks away you are going to rotate the whole board 90 degrees clockwise. Gravity then pulls every piece down in the new orientation.

Start:

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

Right after the clockwise rotation:

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

After gravity finishes:

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

You can rotate the board only once. Gravity acts only after the board has been rotated all the way, and you look for winners only after gravity has finished.

Given a starting position, report which player or players have $K$ pieces in a row once the board has been rotated clockwise and the pieces have settled.

The first line contains the number of test cases $T$. Each test case begins with a line holding two integers $N$ and $K$. The next $N$ lines each hold exactly $N$ characters and describe the starting board in the format above.

Every starting board is a legal position that can occur in a game of Join-K, and neither player already has $K$ pieces in a row.

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

For each test case, print one line in the form Case #x: y, where x is the test case number starting from 1 and y is one of Red, Blue, Neither, or Both. y names the player or players who have $K$ pieces in a row after the rotation and the fall.