Birthday

题意翻译

给定 $n$，初始时你拥有 $n$ 个整数，$1\sim n$ 的每个整数各一个。 你可以进行下列操作至多 $20\times n$ 次： - 选择你拥有的整数 $x,y$，并去掉 $x,y$，在你拥有的整数中加入 $x+y$ 和 $|x-y|$。 你需要使你拥有的整数全部相等，并最小化这些整数。 有解输出任意一组操作，无解输出 `-1`。 每个测试点包含 $T$ 组数据。 $1\leq T\leq2.5\times10^4$，$2\leq n,\sum n\leq5\times10^4$。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #1

2
2
3

输出样例 #1

-1
3
1 3
2 2
4 0