Description

你最近获得了一副新卡牌。每张卡牌显示一个点数（介于 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}$，找到一系列操作，将牌组重新排序为按点数排序（如上所述），并使用尽可能少的操作次数完成。

Input Format

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

Output Format

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

3
2 2
3 2
2 3

Case #1: 1
2 1
Case #2: 2
3 2
2 1
Case #3: 2
2 3
2 2

Hint

样例解释

在样例 #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 完成