C. 或非
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

对于非负整数 $$$x$$$,我们定义 $$$\mathrm{pos} (x, i)$$$ 表示 $$$x$$$ 的第 $$$i$$$ 个二进制位(其中 $$$i \geq 0$$$)。即:

$$$$$$ \mathrm{pos} (x, i) = \left \lfloor \frac{x}{2^i} \right \rfloor - 2 \left \lfloor \frac{x}{2^{i+1}} \right \rfloor $$$$$$

对于两个非负整数 $$$x$$$ 和 $$$y$$$($$$0 \leq x,y \lt 2^{30}$$$),我们定义它们的按位或非 $$$\mathrm{nor} (x, y)$$$ 为:

$$$$$$ \mathrm{nor} (x, y) = \sum_{i=0}^{29} \left [\mathrm{pos} (x, i) = 0 \land \mathrm{pos} (y, i) = 0 \right ] 2^i $$$$$$

其中 $$$[P]$$$ 表示艾弗森括号,当命题 $$$P$$$ 为真时,$$$[P]$$$ 的值为 $$$1$$$,否则为 $$$0$$$。$$$\land$$$ 符号表示逻辑运算。

也就是说,当且仅当 $$$x$$$ 和 $$$y$$$ 的第 $$$i$$$ 位都为 $$$0$$$ 的时候,$$$\mathrm{nor} (x, y)$$$ 的第 $$$i$$$ 位为 $$$1$$$;其余情况下,$$$\mathrm{nor} (x, y)$$$ 的第 $$$i$$$ 位都为 $$$0$$$。

对于两个非负整数 $$$x$$$ 和 $$$y$$$,我们定义它们的按位异或 $$$x \oplus y$$$ 为:

$$$$$$ x \oplus y = \sum_{i=0}^{\infty} \left [\mathrm{pos} (x, i) \neq \mathrm{pos} (y, i) \right ] 2^i $$$$$$

给定一个 $$$n$$$ 个节点的无向完全图,节点编号为 $$$0$$$ 到 $$$n-1$$$。对于每一对满足 $$$0 \leq u \lt v \lt n$$$ 的节点 $$$u$$$ 和 $$$v$$$,$$$u$$$ 和 $$$v$$$ 之间有一条边权为 $$$\mathrm{nor} (u, v)$$$ 的边。

请你找出该图的一个生成树,使得生成树中,所有边的边权的按位异或结果尽可能的小。

Input

第一行包含一个整数 $$$T$$$($$$1 \leq T \leq 10^5$$$),表示一共有 $$$T$$$ 组测试数据。

对于每组测试数据:

  • 仅一行,包含一个整数 $$$n$$$($$$2 \leq n \leq 2 \times 10^5$$$),表示节点数量。

保证测试数据的 $$$n$$$ 的总和不超过 $$$2 \times 10^5$$$。

Output

对于每组测试数据:

  • 输出 $$$n-1$$$ 行,第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$($$$0 \leq u_i, v_i \lt n$$$ 且 $$$u_i \neq v_i$$$),表示你所找到的生成树的第 $$$i$$$ 条边连接 $$$u_i$$$ 和 $$$v_i$$$ 两个节点。
  • 如果有多个满足要求的生成树,你可以输出其中任意一个。
Example
Input
2
5
6
Output
0 2
3 1
3 4
2 4

0 1
1 3
2 5
3 5
4 5
Note

样例的两组数据中,生成树的形态如下图所示。

注意:样例输出中的空行是为了让两组数据的输出更易区分而添加的,你的程序不必输出该空行。