← 返回题目列表

Codeforces · 1930/B

B. 排列打印

中文机器翻译题面 查看原题

给你一个正整数$$$n$$$。

找到长度为 $$$n$$$ 的排列$$$^\dagger$$$ $$$p$$$,使得不存在两个不同的索引 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i, j < n$$$; $$$i \neq j$$$) 使得 $$$p_i$$$ 整除 $$$p_j$$$ $$$p_{i+1}$$$ 除 $$$p_{j+1}$$$。

请参阅注释部分了解一些示例。

在这个问题的约束下,可以证明至少存在一个$$$p$$$。

$$$^\dagger$$$ 长度 $$$n$$$ 的排列是一个数组,由 $$$n$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$ 的任意顺序。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — 排列 $$$p$$$ 的长度。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,输出 $$$p_1, p_2, \ldots, p_n$$$。

如果有多个解,则可以输出其中任意一个。

示例

输入 #1

2
4
3

输出 #1

4 1 2 3
1 2 3

注意

在第一个测试用例中,$$$p=[4,1,2,3]$$$ 是有效的排列。然而,排列 $$$p=[1,2,3,4]$$$ 不是有效的排列,因为我们可以选择 $$$i=1$$$ 和 $$$j=3$$$。然后 $$$p_1=1$$$ 除以 $$$p_3=3$$$,$$$p_2=2$$$ 除以 $$$p_4=4$$$。请注意,排列 $$$p=[3, 4, 2, 1]$$$ 也不是有效的排列,因为我们可以选择 $$$i=3$$$ 和 $$$j=2$$$。然后 $$$p_3=2$$$ 除以 $$$p_2=4$$$,$$$p_4=1$$$ 除以 $$$p_3=2$$$。

在第二个测试用例中,$$$p=[1,2,3]$$$ 是有效的排列。事实上,长度为 $$$3$$$ 的所有 $$$6$$$ 排列都是有效的。