Birthday
Contest: Codeforces Global Round 19
Difficulty rating: 3000
Tags: constructive algorithms, greedy, math

Vitaly gave Maxim $$$n$$$ numbers $$$1, 2, \ldots, n$$$ for his $$$16$$$-th birthday. Maxim was tired of playing board games during the celebration, so he decided to play with these numbers. In one step Maxim can choose two numbers $$$x$$$ and $$$y$$$ from the numbers he has, throw them away, and add two numbers $$$x + y$$$ and $$$|x - y|$$$ instead. He wants all his numbers to be equal after several steps and the sum of the numbers to be minimal.

Help Maxim to find a solution. Maxim's friends don't want to wait long, so the number of steps in the solution should not exceed $$$20n$$$. It is guaranteed that under the given constraints, if a solution exists, then there exists a solution that makes all numbers equal, minimizes their sum, and spends no more than $$$20n$$$ moves.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 25\,000$$$) — the number of test cases.

Each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^4$$$) — the number of integers given to Maxim.

It is guaranteed that the total sum of $$$n$$$ doesn't exceed $$$5 \cdot 10^4$$$.

Output format:
For each test case print $$$-1$$$ if it's impossible to make all numbers equal.

Otherwise print a single integer $$$s$$$ ($$$0 \le s \le 20n$$$) — the number of steps. Then print $$$s$$$ lines. The $$$i$$$-th line must contain two integers $$$x_i$$$ and $$$y_i$$$ — numbers that Maxim chooses on the $$$i$$$-th step. The numbers must become equal after all operations.

Don't forget that you not only need to make all numbers equal, but also minimize their sum. It is guaranteed that under the given constraints, if a solution exists, then there exists a solution that makes all numbers equal, minimizes their sum, and spends no more than $$$20n$$$ moves.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
2
2
3

Example output:
-1
3
1 3
2 2
4 0

Editorial:
The answer is $$$-1$$$ only if $$$n = 2$$$. It will become clear later.
Let all numbers be equal to $$$val$$$ after all steps. Consider the moves in reverse order: numbers $$$x$$$ and $$$y$$$ are obtained from $$$\frac{x + y}{2}$$$ and $$$\frac{|x - y|}{2}$$$. If numbers $$$x$$$ and $$$y$$$ are multiples of an odd number $$$p > 1$$$, then numbers $$$\frac{x + y}{2}$$$ and $$$\frac{|x - y|}{2}$$$ are also multiples of $$$p$$$. But after all steps in reverse order, we need to get $$$1$$$ $$$\Rightarrow$$$ $$$val$$$ can't be a multiple of $$$p$$$. It means that $$$val$$$ is a power of two. Moreover $$$val \ge n$$$ because the maximum after all steps in direct order can't get smaller.
Let's show how to make all numbers equal to the smallest power of two which is at least $$$n$$$.
First of all, let's transform numbers $$$1, 2, \ldots, n$$$ into the $$$n$$$ powers of two (maybe different), but not greater than the answer. Let the function $$$solve(n)$$$ do this. It can be implemented as follows:
1. If $$$n \le 2$$$ then all numbers are already a power of two so we can finish the function.
2. if $$$n$$$ is a power of two, then call $$$solve(n - 1)$$$ and finish the function.
3. Otherwise let's $$$p$$$ be the maximum power of two not exceeding $$$n$$$. Lets make steps by choosing pairs $$$(p - 1, p + 1), (p - 2, p + 2), \ldots, (p - (n - p), p + (n - p))$$$. After that, there will be numbers that can be divided into $$$3$$$ groups:   Numbers that have not been changed: $$$1, 2, \ldots, p - (n - p) - 1$$$ and $$$p$$$. $$$p$$$ is already a power of two. To transform other numbers into the powers of two let's call $$$solve(p - (n - p) - 1)$$$.  Numbers that have been obtained as $$$|x - y|$$$ after some step: $$$2, 4, \ldots, 2 \cdot (n - p)$$$. To transform them into the powers of two we can take the sequence of steps that does $$$solve(n - p)$$$ and multiply all numbers in these steps by $$$2$$$.  All numers that have been obtained as $$$x + y$$$ after some step, are equal to $$$2p$$$ and they are already a power of two.
4. Numbers that have not been changed: $$$1, 2, \ldots, p - (n - p) - 1$$$ and $$$p$$$. $$$p$$$ is already a power of two. To transform other numbers into the powers of two let's call $$$solve(p - (n - p) - 1)$$$.
5. Numbers that have been obtained as $$$|x - y|$$$ after some step: $$$2, 4, \ldots, 2 \cdot (n - p)$$$. To transform them into the powers of two we can take the sequence of steps that does $$$solve(n - p)$$$ and multiply all numbers in these steps by $$$2$$$.
6. All numers that have been obtained as $$$x + y$$$ after some step, are equal to $$$2p$$$ and they are already a power of two.
After this transformation, there are always two equal numbers that are smaller than the answer. Let them be equal to $$$x$$$. Let's make a step using them and we will get $$$0$$$ and $$$2x$$$.
From numbers $$$0$$$ and $$$x$$$ we can get numers $$$0$$$ and $$$2x$$$: $$$(0, x) \rightarrow (x, x) \rightarrow (0, 2x)$$$. So let's just use this $$$0$$$ to transform all remaining numbers into the answer. After all, let's make a step using $$$0$$$ and the answer, so $$$0$$$ becomes equal to the answer.
It is obvious, that this solution works at most in $$$O(n \cdot \log{n})$$$. But at such limits it uses at most $$$7n$$$ steps.