2171E. Anisphia Wynn Palettia and Good Permutations

constructive algorithms,greedy,number theory,*2000

https://codeforces.com/problemset/problem/2171/E

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 𝑎 of length 𝑚, call an index 𝑖 (1≤𝑖≤𝑚−2) bad if 𝑎𝑖, 𝑎𝑖+1, and 𝑎𝑖+2 are all pairwise coprime. More formally, 𝑖 is a bad index if and only if gcd(𝑎𝑖,𝑎𝑖+1)=gcd(𝑎𝑖,𝑎𝑖+2)=gcd(𝑎𝑖+1,𝑎𝑖+2)=1∗. Furthermore, call 𝑎 good if it has at most 6 bad indices.

You are given an integer 𝑛. Construct a good permutation† 𝑝 of length 𝑛. It can be shown that such a permutation always exists.

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

∗gcd(𝑥,𝑦) denotes the greatest common divisor of 𝑥 and 𝑦

† A permutation of length 𝑛 is an array that contains every integer from 1 to 𝑛 exactly once, in any order.

Input

The first line contains a single integer 𝑡 (1≤𝑡≤10^4) — the number of test cases.

The only line of each test case contains a single integer 𝑛 (3≤𝑛≤2⋅10^5).

It is guaranteed that the sum of 𝑛 over all test cases does not exceed 2⋅10^5.

Output

For each test case, output on a single line 𝑛 integers 𝑝1,𝑝2,…,𝑝𝑛, an example of a good permutation of length 𝑛. If there are multiple good permutations, you may output any of them.

Example

Input

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 𝑛=9, we have

𝑖	𝑝𝑖	𝑝𝑖+1	𝑝𝑖+2	gcd(𝑝𝑖,𝑝𝑖+1)	gcd(𝑝𝑖,𝑝𝑖+2)	gcd(𝑝𝑖+1,𝑝𝑖+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≤6, 𝑝 is a good permutation.

【尹显齐 25物理学院】幽默题目，看着难实则很简单。我们先把所有数中能被 $2$ 整除但不能被 $3$ 整除的数找出来，存在第一个数组里，把这些数记为 $a_{1 i}$ ，再把所有能被 $3$ 整除的数存在第二个数组里，把这些数记作 $a_{2 i}$ 。剩下数存在第三个数组里，把这些数记为 $a_{3 i}$ 。然后我们按照如下方式填数：

a_{11}, a_{21}, a_{12}, a_{13}, a_{22}, a_{14}, \dots,

直到把 $a_{1 i}$ 填完，接下来：

a_{31}, a_{2 m}, a_{32}, a_{33}, a_{2 (m + 1)}, a_{34}, \dots

由于三种数的数量大致相等，可以证明在两种填充方式的交界处会出现两个坏位置，末尾至多出现一个坏位置，总共至多出现三个坏位置。

python

for _ in range(int(input())):
    n = int(input())
    ans = []
    even = []
    threes = []
    last = []
    l1,l2,l3 = 0,0,0
    for i in range(1,n+1):
        if i % 3 == 0:
            threes.append(i)
            l3 += 1
        elif i % 2 == 0:
            even.append(i)
            l2 += 1
        else:
            last.append(i)
            l1 += 1
    j = 0
    for i in range(l2):
        ans.append(even[i])
        if i%2 == 0:
            ans.append(last[j])
            j += 1
    for i in range(l3):
        ans.append(threes[i])
        if i%2 == 0 and j < l1:
            ans.append(last[j])
            j += 1
    while j < l1:
        ans.append(last[j])
        j += 1
    print(*ans)

2171E. Anisphia Wynn Palettia and Good Permutations ​

2171E. Anisphia Wynn Palettia and Good Permutations