Problem Description

A "Hongzhuan sequence" of length $n$ is a sequence that satisfies the following properties:

• Each integer from $1$ to $n$ appears in the sequence exactly once.
• The sum of every pair of adjacent elements is not a perfect square.

Given an integer $n$, construct a "Hongzhuan sequence" of length $n$.

Input Format

The first line contains an integer $T$ ($1\le T\le 10^4$), meaning the number of test cases.

For each test case, there is only one line containing one integer $n$ ($1\le n\le 4\times 10^6$), meaning the length of the "Hongzhuan sequence" to construct.

It is guaranteed that the sum of all $n$ does not exceed $4\times 10^6$. It can be proven that under the given conditions, a solution always exists.

Output Format

Output $T$ lines. Each line should be the constructed sequence. If there are multiple solutions, output any one.

5
1
2
3
4
5

1
1 2
1 2 3
1 2 3 4
1 4 2 3 5

Hint

For $n = 5$, if the output is 1 2 3 4 5, it is wrong, because $4 + 5 = 9$ is a perfect square.

Translated by ChatGPT 5