310603: CF1858C. Yet Another Permutation Problem

C. Yet Another Permutation Problemtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Alex got a new game called "GCD permutations" as a birthday present. Each round of this game proceeds as follows:

• First, Alex chooses a permutation$^{\dagger}$ $a_1, a_2, \ldots, a_n$ of integers from $1$ to $n$.
• Then, for each $i$ from $1$ to $n$, an integer $d_i = \gcd(a_i, a_{(i \bmod n) + 1})$ is calculated.
• The score of the round is the number of distinct numbers among $d_1, d_2, \ldots, d_n$.

Alex has already played several rounds so he decided to find a permutation $a_1, a_2, \ldots, a_n$ such that its score is as large as possible.

Recall that $\gcd(x, y)$ denotes the greatest common divisor (GCD) of numbers $x$ and $y$, and $x \bmod y$ denotes the remainder of dividing $x$ by $y$.

$^{\dagger}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input

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

Each test case consists of one line containing a single integer $n$ ($2 \le n \le 10^5$).

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

Output

For each test case print $n$ distinct integers $a_{1},a_{2},\ldots,a_{n}$ ($1 \le a_i \le n$) — the permutation with the largest possible score.

If there are several permutations with the maximum possible score, you can print any one of them.

ExampleInput

4
5
2
7
10

Output

1 2 4 3 5 
1 2 
1 2 3 6 4 5 7 
1 2 3 4 8 5 10 6 9 7

Note

In the first test case, Alex wants to find a permutation of integers from $1$ to $5$. For the permutation $a=[1,2,4,3,5]$, the array $d$ is equal to $[1,2,1,1,1]$. It contains $2$ distinct integers. It can be shown that there is no permutation of length $5$ with a higher score.

In the second test case, Alex wants to find a permutation of integers from $1$ to $2$. There are only two such permutations: $a=[1,2]$ and $a=[2,1]$. In both cases, the array $d$ is equal to $[1,1]$, so both permutations are correct.

In the third test case, Alex wants to find a permutation of integers from $1$ to $7$. For the permutation $a=[1,2,3,6,4,5,7]$, the array $d$ is equal to $[1,1,3,2,1,1,1]$. It contains $3$ distinct integers so its score is equal to $3$. It can be shown that there is no permutation of integers from $1$ to $7$ with a score higher than $3$.

题目大意：
Alex收到了一个名为“GCD排列”的新游戏作为生日礼物。游戏的每一轮按照以下步骤进行：
1. 首先Alex选择一个从1到n的整数排列a1, a2, ..., an。
2. 然后对于每个i从1到n，计算一个整数di = gcd(ai, a((i mod n) + 1))。
3. 这一轮的分数是d1, d2, ..., dn中不同数的数量。

Alex已经玩了几轮，所以他决定找到一个排列a1, a2, ..., an，使其分数尽可能大。

输入输出数据格式：
输入：
第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。
每个测试用例由一行组成，包含一个整数n（2 ≤ n ≤ 10^5）。
保证所有测试用例的n之和不超过10^5。

输出：
对于每个测试用例，打印n个不同的整数a1, a2, ..., an（1 ≤ ai ≤ n）——具有最大可能分数的排列。
如果有多个排列具有最大可能的分数，可以打印其中的任何一个。题目大意： Alex收到了一个名为“GCD排列”的新游戏作为生日礼物。游戏的每一轮按照以下步骤进行： 1. 首先Alex选择一个从1到n的整数排列a1, a2, ..., an。 2. 然后对于每个i从1到n，计算一个整数di = gcd(ai, a((i mod n) + 1))。 3. 这一轮的分数是d1, d2, ..., dn中不同数的数量。 Alex已经玩了几轮，所以他决定找到一个排列a1, a2, ..., an，使其分数尽可能大。 输入输出数据格式： 输入： 第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。 每个测试用例由一行组成，包含一个整数n（2 ≤ n ≤ 10^5）。 保证所有测试用例的n之和不超过10^5。 输出： 对于每个测试用例，打印n个不同的整数a1, a2, ..., an（1 ≤ ai ≤ n）——具有最大可能分数的排列。 如果有多个排列具有最大可能的分数，可以打印其中的任何一个。