B. 排列打印
每个测试点时间限制:1 秒
内存限制:256 兆字节
给你一个正整数 n。
请构造一个长度为 n 的排列 p,使得不存在两个不同的下标 i 和 j(1≤i,j<n,i=j),同时满足:
- pi 整除 pj
- pi+1 整除 pj+1
具体例子可以参考题面最后的“注意”部分。
在本题的数据范围下,可以证明至少存在一个满足条件的排列 p。
† 排列的定义
长度为 n 的排列是一个由 n 个互不相同的整数 1 到 n 按任意顺序组成的数组。
例如,[2,3,1,5,4] 是一个排列,但 [1,2,2] 不是(2 出现了两次),[1,3,4] 也不是(n=3 但数组里出现了 4)。
输入格式
每个测试文件包含多个测试用例。
第一行一个整数 t(1≤t≤103)—— 测试用例的数量。
接下来每个测试用例一行,包含一个整数 n(3≤n≤105)—— 排列的长度 p。
保证所有测试用例的 n 之和不超过 105。
输出格式
对于每个测试用例,输出一行 p1,p2,…,pn。
如果存在多个解,输出任意一个即可。
示例
输入:
2
4
3
输出:
4 1 2 3
1 2 3
注意
-
第一个测试用例中,p=[4,1,2,3] 是一个有效排列。
但 p=[1,2,3,4] 不是有效排列,因为我们可以选 i=1,j=3:
p1=1 整除 p3=3,且 p2=2 整除 p4=4。
另外,p=[3,4,2,1] 也不是有效排列,因为选 i=3,j=2:
p3=2 整除 p2=4,且 p4=1 整除 p3=2。
-
第二个测试用例中,p=[1,2,3] 是有效排列。事实上,长度为 3 的所有 6 个排列都是有效的。