Yet Another Permutation Problem

# 又一个排列问题 ## 题目描述 Alex 收到了一个名为 "GCD 排列" 的游戏作为生日礼物。这个游戏的每一轮进行如下操作： - 首先，Alex 选择一个整数序列 $ ^{\dagger} $ $ a_1, a_2, \ldots, a_n $ ，其中整数范围从 $ 1 $ 到 $ n $ 。 - 然后，对于每个 $ i $ 从 $ 1 $ 到 $ n $ ，计算整数 $ d_i = \gcd(a_i, a_{(i \bmod n) + 1}) $ 。 - 本轮的得分是 $ d_1, d_2, \ldots, d_n $ 中不同数字的数量。 Alex 已经玩了几轮游戏，所以他决定找一个整数序列 $ a_1, a_2, \ldots, a_n $ ，使得它的得分尽可能地大。 回顾一下，$ \gcd(x, y) $ 表示 $ x $ 和 $ y $ 的 [最大公约数（GCD）](https://en.wikipedia.org/wiki/Greatest_common_divisor)，而 $ x \bmod y $ 表示将 $ x $ 除以 $ y $ 的余数。 $ ^{\dagger} $ 长度为 $ n $ 的排列是一个由 $ n $ 个不同整数组成的数组，整数范围从 $ 1 $ 到 $ n $ 且顺序任意。例如，$ [2,3,1,5,4] $ 是一个排列，但 $ [1,2,2] $ 不是排列（数组中有重复的 $ 2 $），$ [1,3,4] $ 也不是排列（虽然 $ n=3 $，但数组中有 $ 4 $）。 ## 输入格式 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $） — 测试用例的数量。 每个测试用例由一行组成，包含一个整数 $ n $（$ 2 \le n \le 10^5 $） — 数列中的整数数量。 保证所有测试用例中的 $ n $ 总和不超过 $ 10^5 $。 ## 输出格式 对于每个测试用例，输出一行包含 $ n $ 个不同整数 $ a_{1},a_{2},\ldots,a_{n} $（$ 1 \le a_i \le n $） — 得分最大的排列。 如果有多个得分相同的排列，可以输出其中任何一个。 ## 样例 #1 ### 样例输入 #1 ``` 4 5 2 7 10 ``` ### 样例输出 #1 ``` 1 2 4 3 5 1 2 1 2 3 6 4 5 7 1 2 3 4 8 5 10 6 9 7 ``` ## 提示 在第一个测试用例中，Alex 想要找一个由整数 $ 1 $ 到 $ 5 $ 组成的排列。对于排列 $ a=[1,2,4,3,5] $，数组 $ d $ 等于 $ [1,2,1,1,1] $。它包含 $ 2 $ 个不同的整数。可以证明，长度为 $ 5 $ 的排列中没有比这个得分更高的。 在第二个测试用例中，Alex 想要找一个由整数 $ 1 $ 到 $ 2 $ 组成的排列。只有两种这样的排列：$ a=[1,2] $ 和 $ a=[2,1] $。在这两种情况下，数组 $ d $ 都等于 $ [1,1] $，所以这两种排列都是正确的。 在第三个测试用例中，Alex 想要找一个由整数 $ 1 $ 到 $ 7 $ 组成的排列。对于排列 $ a=[1,2,3,6,4,5,7] $，数组 $ d $ 等于 $ [1,1,3,2,1,1,1] $。它包含 $ 3 $ 个不同的整数，所以得分等于 $ 3 $。可以证明，由整数 $ 1 $ 到 $ 7 $ 组成的排列中没有得分更高的。

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.

4
5
2
7
10

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

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