← 返回题目列表

Codeforces · 1430/C

C. 白板上的数字

中文机器翻译题面 查看原题

数字 $$$1, 2, 3, \dots n$$$ (从 $$$1$$$ 到 $$$n$$$ 的每个整数一次)写在板上。在一次操作中,您可以从棋盘上擦除任意两个数字 $$$a$$$ 和 $$$b$$$,并写入一个向上舍入的整数 $$$\frac{a + b}{2}$$$。

您应该执行给定的操作 $$$n - 1$$$ 次,并使留在棋盘上的结果数字尽可能小。

例如,如果 $$$n = 4$$$,则以下操作过程是最佳的:

1. 选择$$$a = 4$$$,$$$b = 2$$$,则新数字为$$$3$$$,白板包含$$$[1, 3, 3]$$$;
2. 选择$$$a = 3$$$,$$$b = 3$$$,因此新数字为$$$3$$$,白板包含$$$[1, 3]$$$;
3. 选择$$$a = 1$$$ 和$$$b = 3$$$,因此新数字为$$$2$$$,白板包含$$$[2]$$$。

很容易看出,经过 $$$n - 1$$$ 运算后,只剩下一个数字。您的目标是尽量减少它。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) - 最初写在黑板上的整数的数量。

保证测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在第一行中打印 $$$n - 1$$$ 操作后板上剩余的最小可能数字。接下来的 $$$n - 1$$$ 行应包含两个整数 - 在每次操作中选择并删除的数字 $$$a$$$ 和 $$$b$$$。

示例

输入 #1

1
4

输出 #1

2
2 4
3 3
3 1