帕斯卡三角形由无穷多行整数组成，每行整数的个数递增，排列成三角形。

定义 $(r, k)$ 为第 $r$ 行从左往右数的第 $k$ 个位置，其中 $r$ 和 $k$ 均从 1 开始计数。帕斯卡三角形的定义规则如下：

• 第 $r$ 行包含 $r$ 个位置：$(r, 1), (r, 2), \dots, (r, r)$。
• 对于所有 $r$，位置 $(r, 1)$ 和 $(r, r)$ 上的数字均为 1。
• 对于所有 $2 \le k \le r - 1$，位置 $(r, k)$ 上的数字是位置 $(r - 1, k - 1)$ 和 $(r - 1, k)$ 上数字之和。

帕斯卡三角形的前 5 行如下所示：

在本题中，帕斯卡路径（Pascal walk）是指帕斯卡三角形中满足以下条件的 $S$ 个位置的序列 $(r_1, k_1), (r_2, k_2), \dots, (r_S, k_S)$：

• $r_1 = 1$ 且 $k_1 = 1$。
• 后续的每个位置必须在三角形内，且与前一个位置相邻（六个可能的方向之一）。即对于所有 $i \ge 1$，$(r_{i+1}, k_{i+1})$ 必须是以下在三角形内的位置之一：$(r_i - 1, k_i - 1), (r_i - 1, k_i), (r_i, k_i - 1), (r_i, k_i + 1), (r_i + 1, k_i), (r_i + 1, k_i + 1)$。
• 序列中不得重复出现任何位置。即对于任意 $i \neq j$，满足 $r_i \neq r_j$ 或 $k_i \neq k_j$（或两者皆不相等）。

请找到任意一条长度 $S \le 500$ 的帕斯卡路径，使得路径所经过的所有位置上的数字之和等于 $N$。保证对于每个 $N$，至少存在一条这样的路径。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由包含单个整数 $N$ 的一行组成。

输出格式

对于每个测试用例，首先输出一行 Case #x:，其中 $x$ 是测试用例编号（从 1 开始）。然后，输出你所提出的长度为 $S \le 500$ 的帕斯卡路径，共需 $S$ 行。第 $i$ 行应输出 $r_i \ k_i$，其中 $(r_i, k_i)$ 是路径中的第 $i$ 个位置。例如，第一行应为 1 1，因为所有有效路径的起始位置均为 $(1, 1)$。你所提出的帕斯卡路径中 $S$ 个位置上的数字之和必须恰好为 $N$。

数据范围

时间限制：每个测试集 20 秒。 内存限制：1GB。 $1 \le T \le 100$。

测试集 1（可见判定） $1 \le N \le 501$。

测试集 2（可见判定） $1 \le N \le 1000$。

测试集 3（隐藏判定） $1 \le N \le 10^9$。

样例

输入 1

3
1
4
19

输出 1

Case #1:
1 1
Case #2:
1 1
2 1
2 2
3 3
Case #3:
1 1
2 2
3 2
4 3
5 3
5 2
4 1
3 1

说明

在样例 1 中，仅需起始位置即可。

在样例 2 中，请注意尽管存在更短的路径，但路径不需要是最短的，只要它使用的位置数不超过 500 即可。

下图展示了我们对样例 3 的解法：