P17447 A Simple Construction Problem

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

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 $T$ lines. Each line should be the constructed sequence. If there are multiple solutions, output any one.

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