鸡爪传说中的宝藏

题目描述

给定 $n$ 条边，你可以使用任意个点构造一个简单无向图（不允许自环和重边），要求使图中的“鸡爪”数量尽可能多，并输出这 $n$ 条边各自连接的两个端点。

一个“鸡爪”由 $4$ 个部分组成：一个中心点，以及与它相邻的三条边；这三条边的另外三个端点都不属于这个鸡爪。
一个图上的鸡爪数，定义为最多能找出多少个鸡爪，使得图中的每个点和每条边都至多属于一个鸡爪。

如果存在多种构造方案，请输出其中使得最终输出的 $2n$ 个数字按行优先遍历得到的序列字典序最小的一种。
这里“行优先遍历”是指按输出边的顺序，把每行的两个端点依次拼接成一个长度为 $2n$ 的序列。例如若输出为：

1 2
1 3
1 4

则对应序列为 $\{1,2,1,3,1,4\}$。

数据范围

• $1 \le T \le 2 \times 10^5$
• $1 \le n \le 2 \times 10^5$
• 保证所有测试数据中 $\sum n \le 2 \times 10^5$

输入格式

从标准输入按以下格式读取数据：

$T$

$n$

其中：

• 第一行输入一个整数 $T$，表示测试样例个数。
• 对于每个样例，输入一行一个整数 $n$，表示需要构造的边数。

输出格式

对于每个样例，输出 $n$ 行，每行两个正整数，表示对应一条无向边连接的两个端点。顶点编号从 $1$ 开始。

样例

2
3
5

1 2
1 3
1 4
1 2
1 3
1 4
1 5
1 6