你最近得到了一副新扑克牌。每张牌都有一个点数（rank），是一个介于 $1$ 到 $R$ 之间的整数；还有一个花色（suit），是一个介于 $1$ 到 $S$ 之间的整数。对于点数和花色的每一种组合，都恰好有一张牌，这意味着这副牌总共有 $R \times S$ 张。我们将点数为 $r$、花色为 $s$ 的牌记作 $(r, s)$。

这副新牌最初是按花色从小到大排序的，若花色相同，则按点数从小到大排序。也就是说，$(1, 1)$ 排在最前面，然后是 $(2, 1), \dots, (R, 1)$，接着是 $(1, 2), (2, 2), \dots, (R, 2)$，以此类推，直到 $(R, S)$。例如，当 $R = 4$ 且 $S = 2$ 时，初始顺序为：$(1, 1), (2, 1), (3, 1), (4, 1), (1, 2), (2, 2), (3, 2), (4, 2)$。

你想要重新排列这副牌，使其按点数排序。也就是说，你希望将所有相同点数的牌放在一起，并且点数按从小到大的顺序排列。不过，你并不关心每个点数内部花色的顺序。例如，当 $R = 4$ 且 $S = 2$ 时，一种可能的有效新顺序可以是：$(1, 2), (1, 1), (2, 1), (2, 2), (3, 1), (3, 2), (4, 2), (4, 1)$。

你正在学习烹饪，所以你想在不放下铲子的情况下重新排列这副牌。你决定仅使用以下多步操作来对牌进行排序：

• 首先，从牌堆顶部取出若干张牌，将这些牌设为牌堆 A。
• 接着，从牌堆剩余部分的新顶部取出若干张牌，将这些牌设为牌堆 B。
• 最后，将牌堆 A 放在牌堆顶部，然后将牌堆 B 放在新牌堆的顶部。

注意，该操作交换了牌堆中牌堆 A 部分和牌堆 B 部分的位置，而不影响牌堆中更深处的其他牌（如果有的话）。

继续以 $R = 4, 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)$。

给定 $R$ 和 $S$，请找到一个操作序列，将牌堆按上述要求按点数排序，并使用尽可能少的操作次数。

输入格式

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

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是将牌堆重新排序所需的最少操作次数。然后，打印 $y$ 行，每行包含 $a_i$ 和 $b_i$，表示在操作序列的第 $i$ 次移动中，你首先取出 $a_i$ 张牌形成牌堆 A，然后取出 $b_i$ 张牌形成牌堆 B。

数据范围

内存限制：1GB。

测试集 1（可见判定） 时间限制：30 秒。 $T = 12$。 $2 \le R \le 5$。 $2 \le S \le 7$。 $R \times S \le 14$。

测试集 2（隐藏判定） 时间限制：60 秒。 $1 \le T \le 100$。 $2 \le R \le 40$。 $2 \le S \le 40$。

样例

输入 1

3
2 2
3 2
2 3

输出 1

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

说明

在样例 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$。