Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. What Is It?

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLunar 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

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

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

Example

Input

3 2 3 3

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

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/01/2021 20:25:37 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|