← 返回题目列表

Codeforces · 1637/G

G. 生日

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

Vitaly 给 Maxim $$$n$$$ 数字 $$$1, 2, \ldots, n$$$ 作为他的 $$$16$$$ 生日礼物。马克西姆厌倦了庆祝期间玩棋盘游戏,所以他决定玩这些数字。在一步中,Maxim 可以从他拥有的数字中选择两个数字 $$$x$$$ 和 $$$y$$$,将它们扔掉,然后将两个数字 $$$x + y$$$ 和 $$$|x - y|$$$ 相加。他希望经过几步之后所有的数字都相等,并且数字之和最小。

帮助Maxim找到解决方案。 Maxim的朋友们不想等太久,所以解题的步骤数不要超过$$$20n$$$。保证在给定的约束下,如果存在解决方案,则存在一个使所有数字相等、最小化它们的总和并且花费不超过 $$$20n$$$ 步的解决方案。

输入

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

每个测试用例包含一个整数 $$$n$$$ ($$$2 \le n \le 5 \cdot 10^4$$$) — 给予 Maxim 的整数个数。

保证$$$n$$$的总和不超过$$$5 \cdot 10^4$$$。

输出

对于每个测试用例,如果不可能使所有数字相等,则打印 $$$-1$$$。

否则打印单个整数 $$$s$$$ ($$$0 \le s \le 20n$$$) — 步数。然后打印 $$$s$$$ 行。第 $$$i$$$ 行必须包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ — Maxim 在第 $$$i$$$ 步骤中选择的数字。所有操作后数字必须相等。

不要忘记,您不仅需要使所有数字相等,而且还需要最小化它们的总和。保证在给定的约束下,如果存在解决方案,则存在一个使所有数字相等、最小化它们的总和并且花费不超过 $$$20n$$$ 步的解决方案。

示例

输入 #1

2
2
3

输出 #1

-1
3
1 3
2 2
4 0