What Is It?
Contest: Codeforces Round 696 (Div. 2)
Difficulty rating: 2500
Tags: constructive algorithms, greedy

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.

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.

Input format:
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$$$.

Output format:
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).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
2
3
3

Example output:
1
2 1
1
2 1
5
2 3 1
2
1 3
3 2
5
2 3 1
2
1 3
2 3

Editorial:
Hint $$$1$$$: How many operations will robot make in the worst case?
Hint $$$2$$$: How many times can robot spend $$$(n - 1)^2$$$ time on $$$1$$$ operation?
Hint $$$3$$$: How many times can robot spend $$$(n - 2)^2$$$ time on $$$1$$$ operation? It is easyer to think about number of operations with time greater or equal to $$$(n - 2)^2$$$.
Hint $$$4$$$: Instead of operation from the statement we can apply the following operation to $$$q$$$ which is initially an identity permutation:
• Select $$$i$$$ such that $$$q_i = i$$$ and any $$$j$$$ and swap $$$q_i$$$ and $$$q_j$$$ in $$$(j - i) ^ 2$$$ seconds.
Then we make $$$p$$$ = $$$q$$$ and do operations in reversed order.
Solution:
If we can select $$$i$$$ and $$$j$$$ for an operation, $$$p_j \neq j$$$.
After every operation, there is at least one more element with $$$p_i = i$$$, so after $$$n - 1$$$ operations at least $$$n - 1$$$ elements are on their places. The remaining element can be only on its own place, so we can't do more than $$$n - 1$$$ operations.
Let's now count number of operations that takes $$$(n - 1)^2$$$ time. It is only a swap of $$$1$$$-st and $$$n$$$-th elements. If we did it, $$$p_1 = 1$$$ or $$$p_n = n$$$ so we can't use it one more time. Let's generalize it. If we are calculating number of operations that takes $$$(n - k)^2$$$ time, let's look at the first $$$k$$$ elements and at the last $$$k$$$ elements. Any operation that takes greater or equal then $$$(n - k)^2$$$ seconds, uses two of this elements. So, after $$$2k - 1$$$ operations $$$2k - 1$$$ of this elements will be on their places and we can't use one more operation of this type.
So, $$$answer \leq (n - 1)^2 + (n - 2)^2 + (n - 2)^2 + (n - 3)^2 + \cdots$$$. There are $$$n - 1$$$ terms, each $$$(n - k)^2$$$ appears $$$2$$$ times, except $$$(n - 1)^2$$$ and last term (depends on parity of $$$n - 1$$$).
We can construct example, where robot will spend exactly $$$(n - 1)^2 + (n - 2)^2 + (n - 2)^2 + (n - 3)^2 + \cdots$$$ second as follows (using idea from hint $$$4$$$):
• If $$$n$$$ is even, $$$answer = (n - 1)^2 + \cdots + (n - n / 2)^2 + (n - n / 2)^2$$$. Let's look at the example with $$$n = 6$$$:   Set $$$q = [1, 2, 3, 4, 5, 6]$$$.  Swap $$$q_1$$$ and $$$q_n$$$ in $$$25$$$ seconds, $$$q = [6, 2, 3, 4, 5, 1]$$$.  Swap $$$q_1$$$ and $$$q_{n-1}$$$ in $$$16$$$ seconds, $$$q = [5, 2, 3, 4, 6, 1]$$$.  Swap $$$q_2$$$ and $$$q_n$$$ in $$$16$$$ seconds, $$$q = [5, 1, 3, 4, 6, 2]$$$.  Swap $$$q_1$$$ and $$$q_{n-2}$$$ in $$$9$$$ seconds, $$$q = [4, 1, 3, 5, 6, 2]$$$.  Swap $$$q_3$$$ and $$$q_n$$$ in $$$9$$$ second, $$$q = [4, 1, 2, 5, 6, 3]$$$.  In general, we swap $$$1$$$-st and $$$n$$$-th elements on the first operation and then move elements $$$2, n-1, 3, n-2, 4, n-3, ...$$$ to the further end of $$$q$$$.
• Set $$$q = [1, 2, 3, 4, 5, 6]$$$.
• Swap $$$q_1$$$ and $$$q_n$$$ in $$$25$$$ seconds, $$$q = [6, 2, 3, 4, 5, 1]$$$.
• Swap $$$q_1$$$ and $$$q_{n-1}$$$ in $$$16$$$ seconds, $$$q = [5, 2, 3, 4, 6, 1]$$$.
• Swap $$$q_2$$$ and $$$q_n$$$ in $$$16$$$ seconds, $$$q = [5, 1, 3, 4, 6, 2]$$$.
• Swap $$$q_1$$$ and $$$q_{n-2}$$$ in $$$9$$$ seconds, $$$q = [4, 1, 3, 5, 6, 2]$$$.
• Swap $$$q_3$$$ and $$$q_n$$$ in $$$9$$$ second, $$$q = [4, 1, 2, 5, 6, 3]$$$.
• If $$$n$$$ is odd, $$$answer = (n - 1)^2 + \cdots + (n - \lceil{n/2}\rceil)^2$$$. The only difference from even case is element in the center. For example, if $$$n = 7$$$ we will do the following operations:   $$$q = [1, 2, 3, 4, 5, 6, 7]$$$. Swap $$$q_1$$$ and $$$q_n$$$.  $$$q = [7, 2, 3, 4, 5, 6, 1]$$$. Swap $$$q_1$$$ and $$$q_{n - 1}$$$.  $$$q = [6, 2, 3, 4, 5, 7, 1]$$$. Swap $$$q_2$$$ and $$$q_n$$$.  $$$q = [6, 1, 3, 4, 5, 7, 2]$$$. Swap $$$q_1$$$ and $$$q_{n - 2}$$$.  $$$q = [5, 1, 3, 4, 6, 7, 2]$$$. Swap $$$q_3$$$ and $$$q_n$$$.  $$$q = [5, 1, 2, 4, 6, 7, 3]$$$. Finally, swap $$$q_1$$$ and $$$q_{\lceil{n/2}\rceil}$$$.  $$$q = [4, 1, 2, 5, 6, 7, 3]$$$.
• $$$q = [1, 2, 3, 4, 5, 6, 7]$$$. Swap $$$q_1$$$ and $$$q_n$$$.
• $$$q = [7, 2, 3, 4, 5, 6, 1]$$$. Swap $$$q_1$$$ and $$$q_{n - 1}$$$.
• $$$q = [6, 2, 3, 4, 5, 7, 1]$$$. Swap $$$q_2$$$ and $$$q_n$$$.
• $$$q = [6, 1, 3, 4, 5, 7, 2]$$$. Swap $$$q_1$$$ and $$$q_{n - 2}$$$.
• $$$q = [5, 1, 3, 4, 6, 7, 2]$$$. Swap $$$q_3$$$ and $$$q_n$$$.
• $$$q = [5, 1, 2, 4, 6, 7, 3]$$$. Finally, swap $$$q_1$$$ and $$$q_{\lceil{n/2}\rceil}$$$.
• $$$q = [4, 1, 2, 5, 6, 7, 3]$$$.