You have an array $$$a_1, a_2, \dots, a_n$$$ where $$$a_i = i$$$.
In one step, you can choose two indices $$$x$$$ and $$$y$$$ ($$$x \neq y$$$) and set $$$a_x = \left\lceil \frac{a_x}{a_y} \right\rceil$$$ (ceiling function).
Your goal is to make array $$$a$$$ consist of $$$n - 1$$$ ones and $$$1$$$ two in no more than $$$n + 5$$$ steps. Note that you don't have to minimize the number of steps.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.
The first and only line of each test case contains the single integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the length of array $$$a$$$.
It's guaranteed that the sum of $$$n$$$ over test cases doesn't exceed $$$2 \cdot 10^5$$$.
For each test case, print the sequence of operations that will make $$$a$$$ as $$$n - 1$$$ ones and $$$1$$$ two in the following format: firstly, print one integer $$$m$$$ ($$$m \le n + 5$$$) — the number of operations; next print $$$m$$$ pairs of integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$; $$$x \neq y$$$) ($$$x$$$ may be greater or less than $$$y$$$) — the indices of the corresponding operation.
It can be proven that for the given constraints it's always possible to find a correct sequence of operations.
2 3 4
2 3 2 3 2 3 3 4 4 2 4 2
In the first test case, you have array $$$a = [1, 2, 3]$$$. For example, you can do the following:
In the second test case, $$$a = [1, 2, 3, 4]$$$. For example, you can do the following:
Name |
---|