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.

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.

Anisphia Wynn Palettia and Good Permutations

Examples