CF1474E.What Is It?

Lunar rover finally reached planet X. After landing, he met an obstacle, that contains permutation $p$ of length $n$. Scientists found out, that to overcome an obstacle, the robot should make $p$ an identity permutation (make $p_i = i$ for all $i$).

Unfortunately, scientists can't control the robot. Thus the only way to make $p$ an identity permutation is applying the following operation to $p$ multiple times:

• Select two indices $i$ and $j$ ($i \neq j$), such that $p_j = i$ and swap the values of $p_i$ and $p_j$. It takes robot $(j - i)^2$ seconds to do this operation.

Positions $i$ and $j$ are selected by the robot (scientists can't control it). He will apply this operation while $p$ isn't an identity permutation. We can show that the robot will make no more than $n$ operations regardless of the choice of $i$ and $j$ on each operation.

Scientists asked you to find out the maximum possible time it will take the robot to finish making $p$ an identity permutation (i. e. worst-case scenario), so they can decide whether they should construct a new lunar rover or just rest and wait. They won't believe you without proof, so you should build an example of $p$ and robot's operations that maximizes the answer.

For a better understanding of the statement, read the sample description.

月球车终于抵达了行星 X。着陆后，它遇到了一个障碍物，该障碍物包含一个长度为 $n$ 的排列 $p$。科学家们发现，要克服这一障碍，机器人必须将 $p$ 变为单位排列（即对所有 $i$ 满足 $p_i = i$）。

不幸的是，科学家无法控制机器人。因此，将 $p$ 变为单位排列的唯一方法是多次对 $p$ 执行如下操作：

• 选择两个下标 $i$ 和 $j$（$i \neq j$），满足 $p_j = i$，然后交换 $p_i$ 和 $p_j$ 的值。机器人执行此操作耗时 $(j - i)^2$ 秒。

下标 $i$ 和 $j$ 由机器人自行选定（科学家无法干预）。只要 $p$ 尚未成为单位排列，机器人便会持续执行该操作。可以证明：无论每次操作中 $i$ 和 $j$ 如何选取，机器人至多执行 $n$ 次操作。

科学家请你计算机器人将 $p$ 变为单位排列所需的最大可能时间（即最坏情况），以便他们决定是否需要建造一辆新的月球车，还是只需休息等待即可。他们不会轻信你的结论，因此你必须构造一个具体的排列 $p$ 及其对应的一系列机器人操作，使得总耗时达到该最大值。

为更好理解题意，请参阅样例说明。

The first line of input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

Each of next $t$ lines contains the single integer $n$ ($2 \leq n \leq 10^5$) – the length of $p$.

Note, that $p$ is not given to you. You should find the maximum possible time over all permutations of length $n$.

It is guaranteed, that the total sum of $n$ over all test cases doesn't exceed $10^5$.

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

接下来的 $t$ 行中，每行包含一个整数 $n$（$2 \leq n \leq 10^5$）——排列 $p$ 的长度。

注意：$p$ 并未直接给出。你需要在所有长度为 $n$ 的排列中找出可能的最大时间。

保证所有测试用例的 $n$ 值之和不超过 $10^5$。

For each test case in the first line, print how many seconds will the robot spend in the worst case.

In the next line, print the initial value of $p$ that you used to construct an answer.

In the next line, print the number of operations $m \leq n$ that the robot makes in your example.

In the each of next $m$ lines print two integers $i$ and $j$ — indices of positions that the robot will swap on this operation. Note that $p_j = i$ must holds (at the time of operation).

对于每个测试用例，第一行输出机器人在最坏情况下将花费多少秒。

下一行输出你用于构造答案的初始值 $p$。

再下一行输出你的示例中机器人执行的操作次数 $m \leq n$。

接下来的 $m$ 行中，每行输出两个整数 $i$ 和 $j$ —— 表示机器人在该操作中将要交换的位置索引。注意：在执行该操作时必须满足 $p_j = i$。

For $n = 2$, $p$ can be either $[1, 2]$ or $[2, 1]$. In the first case $p$ is already identity, otherwise robot will make it an identity permutation in $1$ second regardless of choise $i$ and $j$ on the first operation.

For $n = 3$, $p$ can be equals $[2, 3, 1]$.

• If robot will select $i = 3, j = 2$ on the first operation, $p$ will become $[2, 1, 3]$ in one second. Now robot can select only $i = 1, j = 2$ or $i = 2, j = 1$. In both cases, $p$ will become identity in one more second ($2$ seconds in total).
• If robot will select $i = 1, j = 3$ on the first operation, $p$ will become $[1, 3, 2]$ in four seconds. Regardless of choise of $i$ and $j$ on the second operation, $p$ will become identity in five seconds.

We can show, that for permutation of length $3$ robot will always finish all operation in no more than $5$ seconds.

当 $n = 2$ 时，$p$ 可以是 $[1, 2]$ 或 $[2, 1]$。在第一种情况下，$p$ 已经是恒等排列；在第二种情况下，无论机器人在第一次操作中选择哪一对 $i$ 和 $j$，均能在 $1$ 秒内将其变为恒等排列。

当 $n = 3$ 时，$p$ 可以等于 $[2, 3, 1]$。

• 若机器人在第一次操作中选择 $i = 3, j = 2$，则 $p$ 将在 $1$ 秒后变为 $[2, 1, 3]$。此时机器人只能选择 $i = 1, j = 2$ 或 $i = 2, j = 1$。在这两种情况下，$p$ 都将在再经过 $1$ 秒后变为恒等排列（总计 $2$ 秒）。
• 若机器人在第一次操作中选择 $i = 1, j = 3$，则 $p$ 将在 $4$ 秒后变为 $[1, 3, 2]$。无论在第二次操作中如何选择 $i$ 和 $j$，$p$ 都将在 $5$ 秒后变为恒等排列。

我们可以证明：对于长度为 $3$ 的排列，机器人总能在不超过 $5$ 秒的时间内完成所有操作。