Description

帕斯卡三角形 由无限多行整数构成，每行的整数数量逐行递增，排列成三角形。

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

• 第 $r$ 行包含 $r$ 个位置 $(r, 1), (r, 2), \ldots, (r, r)$。
• 对于所有 $r$，位置 $(r, 1)$ 和 $(r, r)$ 的数字均为 $1$。
• 对于所有满足 $2 \leqslant k \leqslant r-1$ 的 $k$，位置 $(r, k)$ 的数字等于位置 $(r-1, k-1)$ 和 $(r-1, k)$ 的数字之和。

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

在本问题中，帕斯卡游走 是指帕斯卡三角形中一个长度为 $\mathrm{s}$ 的位置序列 $\left(\mathrm{r}_{1}, \mathrm{k}_{1}\right), \left(\mathrm{r}_{2}, \mathrm{k}_{2}\right), \ldots, \left(\mathrm{r}_{\mathrm{s}}, \mathrm{k}_{\mathrm{s}}\right)$，满足以下条件：

1. $\mathrm{r}_{1}=1$ 且 $\mathrm{k}_{1}=1$。
2. 每个后续位置必须在三角形内，并且与前一个位置相邻（六个可能方向之一）。即对于所有 $\mathrm{i} \geqslant 1$，$\left(\mathrm{r}_{\mathrm{i}+1}, \mathrm{k}_{\mathrm{i}+1}\right)$ 必须是以下之一且位于三角形内：$\left(\mathrm{r}_{\mathrm{i}}-1, \mathrm{k}_{\mathrm{i}}-1\right)$、$\left(\mathrm{r}_{\mathrm{i}}-1, \mathrm{k}_{\mathrm{i}}\right)$、$\left(\mathrm{r}_{\mathrm{i}}, \mathrm{k}_{\mathrm{i}}-1\right)$、$\left(\mathrm{r}_{\mathrm{i}}, \mathrm{k}_{\mathrm{i}}+1\right)$、$\left(\mathrm{r}_{\mathrm{i}}+1, \mathrm{k}_{\mathrm{i}}\right)$、$\left(\mathrm{r}_{\mathrm{i}}+1, \mathrm{k}_{\mathrm{i}}+1\right)$。
3. 序列中不能重复访问同一位置。即对于任意 $\mathrm{i} \neq \mathrm{j}$，必须满足 $\mathrm{r}_{\mathrm{i}} \neq \mathrm{r}_{\mathrm{j}}$ 或 $\mathrm{k}_{\mathrm{i}} \neq \mathrm{k}_{\mathrm{j}}$，或两者均不相等。

请构造一个长度 $\mathrm{S} \leqslant 500$ 的帕斯卡游走，使得所访问位置中所有数字之和恰好等于 $\mathrm{N}$。题目保证对于所有 $\mathrm{N}$，至少存在一个这样的游走。

Input Format

输入的第一行包含测试用例数量 $\mathrm{T}$。随后是 $\mathrm{T}$ 个测试用例，每个用例占一行，包含一个整数 $\mathrm{N}$。

Output Format

对于每个测试用例，首先输出一行 Case #x:，其中 $\mathrm{x}$ 为测试用例编号（从 1 开始）。接着输出你构造的帕斯卡游走，共 $\mathrm{S} \leqslant 500$ 行，每行格式为 $\mathrm{r}_{\mathrm{i}} \ \mathrm{k}_{\mathrm{i}}$，表示游走的第 $\mathrm{i}$ 个位置 $\left(\mathrm{r}_{\mathrm{i}}, \mathrm{k}_{\mathrm{i}}\right)$。例如，第一行必须为 1 1，因为所有有效游走的起点均为 $(1,1)$。游走中所有位置的数字之和必须严格等于 $\mathrm{N}$。

3
1
4
19

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

Hint

说明/提示

样例解释

• 样例 #1 仅需起点位置即可满足要求。

• 样例 #2 中，虽然存在更短的路径，但路径长度只需不超过 500 即可，无需最短。

• 下图展示了样例 #3 的解决方案：

数据范围

• $1 \leqslant \mathrm{T} \leqslant 100$。

测试集 1（3 分，可见评测结果）

• $1 \leqslant \mathrm{N} \leqslant 501$。

测试集 2（11 分，可见评测结果）

• $1 \leqslant \mathrm{N} \leqslant 1000$。

测试集 3（21 分，隐藏评测结果）

• $1 \leqslant \mathrm{N} \leqslant 10^{9}$。

翻译由 DeepSeek V3 完成