← 返回题目列表

Codeforces · 1469/D

D. 天花板划分

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

你有一个数组 $$$a_1, a_2, \dots, a_n$$$ 其中 $$$a_i = i$$$。

一步中,您可以选择两个索引 $$$x$$$ 和 $$$y$$$ ($$$x \neq y$$$) 并设置 $$$a_x = \left\lceil \frac{a_x}{a_y} \right\rceil$$$ (ceiling function)。

您的目标是使数组 $$$a$$$ 由 $$$n - 1$$$ 和 $$$1$$$ 两个组成,步骤不超过 $$$n + 5$$$。请注意,您不必最小化步骤数。

输入

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

每个测试用例的第一行也是唯一一行包含单个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

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

输出

对于每个测试用例,按以下格式打印使 $$$a$$$ 为 $$$n - 1$$$ 和 $$$1$$$ 为 2 的操作序列:首先,打印一个整数 $$$m$$$ ($$$m \le n + 5$$$) — 操作数;接下来打印 $$$m$$$ 整数对 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$; $$$x \neq y$$$) ($$$x$$$ 可能大于或小于 $$$y$$$) — 相应操作的索引。

可以证明,对于给定的约束,总是可以找到正确的操作序列。

示例

输入 #1

2
3
4

输出 #1

2
3 2
3 2
3
3 4
4 2
4 2

注意

在第一个测试用例中,您有数组 $$$a = [1, 2, 3]$$$。例如,您可以执行以下操作:

1. 选择$$$3$$$, $$$2$$$: $$$a_3 = \left\lceil \frac{a_3}{a_2} \right\rceil = 2$$$ 和数组$$$a = [1, 2, 2]$$$;
2. 选择 $$$3$$$、$$$2$$$:$$$a_3 = \left\lceil \frac{2}{2} \right\rceil = 1$$$ 和数组 $$$a = [1, 2, 1]$$$。

在第二个测试用例中,$$$a = [1, 2, 3, 4]$$$。例如,您可以执行以下操作:

1. 选择 $$$3$$$, $$$4$$$: $$$a_3 = \left\lceil \frac{3}{4} \right\rceil = 1$$$ 和数组 $$$a = [1, 2, 1, 4]$$$;
2. 选择 $$$4$$$, $$$2$$$: $$$a_4 = \left\lceil \frac{4}{2} \right\rceil = 2$$$ 和数组 $$$a = [1, 2, 1, 2]$$$;
3. 选择 $$$4$$$、$$$2$$$:$$$a_4 = \left\lceil \frac{2}{2} \right\rceil = 1$$$ 和数组 $$$a = [1, 2, 1, 1]$$$。