Havannah 是一款由 Christian Freeling 创造的抽象策略棋盘游戏。Havannah 在一个每条边有 $S$ 个六边形的六边形棋盘上进行。每个六边形有两条水平边和四条倾斜边。六边形由一对整数值标识。棋盘底角的六边形为 $(1, 1)$。 与 $(x, y)$ 在两点钟方向相邻的六边形是 $(x, y+1)$。与 $(x, y)$ 在十点钟方向相邻的六边形是 $(x + 1, y)$。

以下是一个 $S = 5$ 的棋盘示例：

在 Havannah 游戏中，每个六边形最多只能被放置一颗棋子。棋子一旦放置在棋盘上，就不会被移除或移动。游戏的目标是利用棋子构建出三种特定类型的连通棋子集合。 获胜结构包括：

• 一个环（ring），环绕着一个或多个空的六边形。也就是说，内部至少有一个六边形必须是空的。更具体地说，存在一个空六边形，它被棋子构成的环与棋盘的最外边界隔开。注意：此规则与官方 Havannah 游戏规则不同。
• 一个桥（bridge），连接棋盘的任意两个角。
• 一个叉（fork），连接棋盘六条边中的任意三条。 角不计入任何相邻的边。

下图展示了获胜结构的示例：

你的程序需要确定单名玩家的一系列落子是否构建出了获胜结构。如果是，则输出结构的名称以及完成该结构的落子步数。如果某一步落子同时完成了多个环、连接了超过两个角或连接了超过三条边，该结构仍分别被视为环、桥或叉。但如果某一步落子同时完成了不同类型的结构，你的程序应输出所有这些结构的名称。我们只关心第一次获胜的落子：忽略获胜落子之后的所有落子。 如果在执行完序列中的所有落子后，棋盘上没有获胜结构，你的程序应输出 none。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $S$ 和 $M$，分别表示棋盘每条边的六边形数量和落子序列的步数。接下来的 $M$ 行按顺序提供落子序列，每行包含一对空格分隔的六边形标识符 $(x, y)$。序列中的所有落子均位于大小为 $S$ 的棋盘内。在每个测试用例中，棋盘初始为空，且落子不会重复。

输出格式

对于每个测试用例，输出一行，格式为 "Case #$n$: "，后跟以下内容之一：

• none
• bridge in move $k$
• fork in move $k$
• ring in move $k$
• bridge-fork in move $k$
• bridge-ring in move $k$
• fork-ring in move $k$
• bridge-fork-ring in move $k$

测试用例编号从 1 开始。落子步数从 1 开始计数。

数据范围

内存限制：1GB。

子任务

测试集 1

时间限制：6 秒。

$1 \le T \le 200$

$2 \le S \le 50$

$0 \le M \le 100$

测试集 2

时间限制：12 秒。

$1 \le T \le 20$

$2 \le S \le 3000$

$0 \le M \le 10000$

样例

输入 1

7
2 4
1 1
1 2
2 3
3 3
3 6
2 1
2 2
2 3
2 4
1 2
4 4
3 7
3 3
2 2
2 3
3 4
4 4
4 3
3 2
3 6
2 2
2 3
3 4
4 4
4 3
3 2
3 8
1 1
2 1
1 3
2 4
1 2
3 2
3 3
3 4
3 7
1 1
2 2
3 5
3 4
5 3
4 3
3 3
3 3
1 1
1 3
3 5

输出 1

Case #1: bridge in move 2
Case #2: fork in move 5
Case #3: none
Case #4: ring in move 6
Case #5: bridge-fork in move 5
Case #6: bridge in move 7
Case #7: none