E. Anisphia Wynn Palettia and Good Permutations
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
I've always loved the word magic. It has a way of making people happy, of putting a smile on their faces.
— Anisphia Wynn Palettia

Anis and her new assistant Euphie are improving the Witch's Broom! Magicology requires great precision and care — in order to fly, the construction of the broom must have sufficiently few imperfections.

For an arbitrary array $$$a$$$ of length $$$m$$$, call an index $$$i$$$ ($$$1\leq i\leq m-2$$$) bad if $$$a_i$$$, $$$a_{i+1}$$$, and $$$a_{i+2}$$$ are all pairwise coprime. More formally, $$$i$$$ is a bad index if and only if $$$\gcd(a_i, a_{i+1}) = \gcd(a_i, a_{i+2}) = \gcd(a_{i+1}, a_{i+2}) = 1$$$$$$^{\text{∗}}$$$. Furthermore, call $$$a$$$ good if it has at most $$$6$$$ bad indices.

You are given an integer $$$n$$$. Construct a good permutation$$$^{\text{†}}$$$ $$$p$$$ of length $$$n$$$. It can be shown that such a permutation always exists.

Note that you do not have to minimize the number of bad indices.

$$$^{\text{∗}}$$$$$$\gcd(x, y)$$$ denotes the greatest common divisor of $$$x$$$ and $$$y$$$

$$$^{\text{†}}$$$ A permutation of length $$$n$$$ is an array that contains every integer from $$$1$$$ to $$$n$$$ exactly once, in any order.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$)  — the number of test cases.

The only line of each test case contains a single integer $$$n$$$ ($$$3\leq n \leq 2\cdot 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output on a single line $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$, an example of a good permutation of length $$$n$$$. If there are multiple good permutations, you may output any of them.

Example
Input
4
3
6
8
9
Output
2 1 3
4 1 6 3 5 2
4 1 6 3 5 2 8 7
5 4 8 1 9 3 6 2 7
Note

For $$$n=9$$$, we have

$$$i$$$$$$p_i$$$$$$p_{i+1}$$$$$$p_{i+2}$$$$$$\gcd(p_i, p_{i+1})$$$$$$\gcd(p_i, p_{i+2})$$$$$$\gcd(p_{i+1}, p_{i+2})$$$
$$$1$$$$$$5$$$$$$4$$$$$$8$$$$$$1$$$$$$1$$$$$$4$$$
$$$2$$$$$$4$$$$$$8$$$$$$1$$$$$$4$$$$$$1$$$$$$1$$$
$$$3$$$$$$8$$$$$$1$$$$$$9$$$$$$1$$$$$$1$$$$$$1$$$
$$$4$$$$$$1$$$$$$9$$$$$$3$$$$$$1$$$$$$1$$$$$$3$$$
$$$5$$$$$$9$$$$$$3$$$$$$6$$$$$$3$$$$$$3$$$$$$3$$$
$$$6$$$$$$3$$$$$$6$$$$$$2$$$$$$3$$$$$$1$$$$$$2$$$
$$$7$$$$$$6$$$$$$2$$$$$$7$$$$$$2$$$$$$1$$$$$$1$$$

The only bad index is $$$3$$$. Since $$$1\leq 6$$$, $$$p$$$ is a good permutation.