← 返回题目列表

Codeforces · 2162/G

G. 美丽的树

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

树是没有循环的连通图。

一棵树被称为 美丽 如果其所有边的顶点标签的乘积之和是 完美正方形.

更正式地说,令 $$$E$$$ 为树中的边集。这棵树叫 美丽 如果值 $$S = \sum_{\{u, v\} \in E} (u \cdot v)$$ 是完全平方数。也就是说,存在一个整数 $$$x$$$ 使得 $$$S = x^2$$$。

给你一个整数$$$n$$$。您的任务是构造一棵具有 $$$n$$$ 个顶点的美丽树,或者报告这样的树不存在。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例包含一个整数 $$$n$$$ ($$$2 \le n \le 2\cdot10^5$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,如果没有美丽的树具有 $$$n$$$ 顶点,则打印 $$$-1$$$。

否则,打印 $$$n-1$$$ 行,表示具有 $$$n$$$ 顶点的美丽树的边缘。每行应包含两个空格分隔的整数 $$$u,v$$$ ($$$1 \le u,v \le n$$$) 表示一条边。

边内的顶点可以按任意顺序打印,边也可以按任意顺序打印。

示例

输入
复制

3
2
3
4

输出
复制

-1
1 3
2 3
1 2
3 1
4 1

注意

测试用例1: 不存在具有 $$$2$$$ 顶点的美丽树。因此,打印$$$-1$$$。

测试用例2:

$$$S = (2\cdot3) + (1\cdot3) = 9 = (3)^2$$$

测试用例3:

$$$S = (2\cdot1) + (3\cdot1) + (4\cdot1) = 9 = (3)^2$$$