A13990 | 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.

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$ .

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).