A16119 | Yet Another Permutation Problem

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

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

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.