CF2171E Anisphia Wynn Palettia and Good Permutations

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](https://en.wikipedia.org/wiki/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.

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

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.

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.