P13058 [GCJ 2020 #1B] Join the Ranks

你最近获得了一副新卡牌。每张卡牌显示一个**点数**（介于 1 和 $\mathbf{R}$ 之间的整数）和一个**花色**（介于 1 和 $\mathbf{S}$ 之间的整数）。对于每个点数和花色的组合，恰好有一张对应的卡牌，这意味着这副牌共有 $\mathbf{R} \times \mathbf{S}$ 张。我们将点数为 $r$、花色为 $s$ 的卡牌记为 $(r, s)$。 由于是全新的牌组，初始时卡牌按花色从小到大排序，相同花色时按点数从小到大排序。也就是说，$(1, 1)$ 在最上面，接着是 $(2, 1)$，……，$(\mathbf{R}, 1)$，然后是 $(1, 2)$，$(2, 2)$，……，$(\mathbf{R}, 2)$，依此类推直到 $(\mathbf{R}, \mathbf{S})$。例如，$\mathbf{R} = 4$ 点、$\mathbf{S} = 2$ 花色时，初始顺序为：$(1, 1)$，$(2, 1)$，$(3, 1)$，$(4, 1)$，$(1, 2)$，$(2, 2)$，$(3, 2)$，$(4, 2)$。 你希望重新排列牌组，使其按点数排序。也就是说，你想将所有相同点数的卡牌放在一起，并按点数升序排列。但你不在乎每个点数内部花色的顺序。例如，$\mathbf{R} = 4$ 和 $\mathbf{S} = 2$ 时，一种可能的有效新顺序是：$(1, 2)$，$(1, 1)$，$(2, 1)$，$(2, 2)$，$(3, 1)$，$(3, 2)$，$(4, 2)$，$(4, 1)$。 你最近在学习烹饪，因此希望在不放下锅铲的情况下完成牌组排序。你决定仅使用以下多步操作来排序牌组： 1. 首先，从牌组顶部取一张或多张卡牌，作为堆叠 A。 2. 接着，从新的牌组顶部再取一张或多张卡牌，作为堆叠 B。 3. 最后，将堆叠 A 放回牌组顶部，再将堆叠 B 放在新的牌组顶部。 注意，该操作交换了牌组的堆叠 A 部分和堆叠 B 部分，而不会影响更深层的卡牌（如果有的话）。 继续以 $\mathbf{R} = 4$、$\mathbf{S} = 2$ 为例，如果第一次操作选择 3 张卡牌作为堆叠 A，2 张作为堆叠 B，则得到： - A：$(1, 1)$，$(2, 1)$，$(3, 1)$， - B：$(4, 1)$，$(1, 2)$， - 剩余牌组：$(2, 2)$，$(3, 2)$，$(4, 2)$。 将 A 放回牌组后再放上 B，新的牌组顺序为： $(4, 1)$，$(1, 2)$，$(1, 1)$，$(2, 1)$，$(3, 1)$，$(2, 2)$，$(3, 2)$，$(4, 2)$。 给定 $\mathbf{R}$ 和 $\mathbf{S}$，找到一系列操作，将牌组重新排序为按点数排序（如上所述），并使用尽可能少的操作次数完成。

输入的第一行包含测试用例的数量 $\mathbf{T}$。接下来的 $\mathbf{T}$ 行每行描述一个测试用例，包含两个整数 $\mathbf{R}$ 和 $\mathbf{S}$，分别表示牌组的点数和花色数量。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是重新排序牌组所需的最少操作次数。然后，输出 $y$ 行，每行包含 $a_{i}$ $b_{i}$，表示在第 $i$ 次操作中，先取 $a_{i}$ 张卡牌作为堆叠 A，再取 $b_{i}$ 张卡牌作为堆叠 B。

**样例解释** 在样例 #1 中，初始顺序为 $(1, 1)$，$(2, 1)$，$(1, 2)$，$(2, 2)$。交换 $A = (1, 1)$，$(2, 1)$ 和 $B = (1, 2)$ 后，牌组变为 $(1, 2)$，$(1, 1)$，$(2, 1)$，$(2, 2)$，满足按点数排序的要求。注意，每个点数内部的花色顺序可以不同，这是允许的。 在样例 #2 中，初始顺序为 $(1, 1)$，$(2, 1)$，$(3, 1)$，$(1, 2)$，$(2, 2)$，$(3, 2)$。第一次操作交换 $A = (1, 1)$，$(2, 1)$，$(3, 1)$ 和 $B = (1, 2)$，$(2, 2)$ 后，牌组变为 $(1, 2)$，$(2, 2)$，$(1, 1)$，$(2, 1)$，$(3, 1)$，$(3, 2)$。第二次操作交换 $A = (1, 2)$，$(2, 2)$ 和 $B = (1, 1)$ 后，牌组变为 $(1, 1)$，$(1, 2)$，$(2, 2)$，$(2, 1)$，$(3, 1)$，$(3, 2)$。 在样例 #3 中，另一种有效解法是第一次操作 $a_{1} = 4$，$b_{1} = 1$，第二次操作 $a_{2} = 3$，$b_{2} = 1$。 **数据范围** **测试集 1（14 分，可见判定）** - 时间限制：30 秒。 - $\mathbf{T} = 12$。 - $2 \leq \mathbf{R} \leq 5$。 - $2 \leq \mathbf{S} \leq 7$。 - $\mathbf{R} \times \mathbf{S} \leq 14$。 **测试集 2（23 分，隐藏判定）** - 时间限制：60 秒。 - $1 \leq \mathbf{T} \leq 100$。 - $2 \leq \mathbf{R} \leq 40$。 - $2 \leq \mathbf{S} \leq 40$。 翻译由 DeepSeek V3 完成