你有一个数组 $$$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]$$$。