Description

在激动人心的 Join-$K$ 游戏中，红色和蓝色棋子被投入一个 $N \times N$ 的棋盘。棋盘是竖直放置的，因此棋子会下落到该列最底部的空位。例如，考虑以下两种棋盘状态：

    - 合法状态 -

          .......
          .......
          .......
          ....R..
          ...RB..
          ..BRB..
          .RBBR..
   - 非法状态 -

          .......
          .......
          .......
          .......
   错误 -> ..BR...
          ...R...
          .RBBR..

在这些图中，每个 '.' 表示一个空位，每个 'R' 表示一个红色棋子，每个 'B' 表示一个蓝色棋子。左边的状态是合法的，而右边的状态不是。原因是第三列中有一个棋子（箭头所指）没有落到其下方的空位上。

如果某个玩家能够将至少 $K$ 个同色棋子连成一行（可以是横向、纵向或对角线），则该玩家获胜。四种可能的连线方向如下所示：

      - 四连子 -

     R   RRRR    R   R
     R          R     R
     R         R       R
     R        R         R

在题目开头的“合法状态”示意图中，两个玩家都已经连成了两个棋子，但都没有连成三个。

现在，你正处于一场激烈的 Join-$K$ 游戏中，并且你有一个巧妙的计划确保获胜！当你的对手不注意时，你准备将棋盘顺时针旋转 $90$ 度。然后，重力会让棋子在新方向上再次下落，形成如下状态：

    - 初始 -

     .......
     .......
     .......
     ...R...
     ...RB..
     ..BRB..
     .RBBR..
   - 旋转 -

     .......
     R......
     BB.....
     BRRR...
     RBB....
     .......
     .......
   - 重力作用 -

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

不幸的是，你只有一次旋转的机会，在对手发现之前。

现在只剩下选择合适的时机出手了。给定一个棋盘状态，请你判断在顺时针旋转棋盘并让重力生效后，哪一方（或双方！）会在棋盘上连成 $K$ 个棋子。

注意

• 你只能旋转棋盘一次。
• 假设重力只在棋盘完全旋转后才会生效。
• 只有在重力作用结束后才检查是否有玩家获胜。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据，每组测试数据的第一行为两个整数 $N$ 和 $K$。接下来的 $N$ 行，每行恰好 $N$ 个字符，表示棋盘的初始状态，格式与上文示意图一致。

每组测试数据中的初始状态都是 Join-$K$ 游戏中可能出现的合法状态。特别地，初始状态下不会有玩家已经连成 $K$ 个棋子。

Output Format

对于每组测试数据，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 为 "Red"、"Blue"、"Neither" 或 "Both" 之一，表示在旋转棋盘并让重力生效后，哪一方（或双方）会连成 $K$ 个棋子。

4
7 3
.......
.......
.......
...R...
...BB..
..BRB..
.RRBR..
6 4
......
......
.R...R
.R..BB
.R.RBR
RB.BBB
4 4
R...
BR..
BR..
BR..
3 3
B..
RB.
RB.

Case #1: Neither
Case #2: Both
Case #3: Red
Case #4: Blue

Hint

数据范围

• $1 \leqslant T \leqslant 100$。
• $3 \leqslant K \leqslant N$。

小数据范围（11 分，测试点 1 - 可见）

• $3 \leqslant N \leqslant 7$。

大数据范围（12 分，测试点 2 - 隐藏）

• $3 \leqslant N \leqslant 50$。

由 ChatGPT 4.1 翻译