← 返回题目列表

Codeforces · 1712/B

B. 可悲的排列

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

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

找到长度为 $$$n$$$ 的任意排列 $$$p$$$,使得总和 $$$\operatorname{lcm}(1,p_1) + \operatorname{lcm}(2, p_2) + \ldots + \operatorname{lcm}(n, p_n)$$$ 尽可能大。

这里 $$$\operatorname{lcm}(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最小公倍数 (LCM)。

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

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1\,000$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。

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

输出

对于每个测试用例,打印 $$$n$$$ 整数 $$$p_1$$$、$$$p_2$$$、$$$\ldots$$$、$$$p_n$$$ - 最大可能值为 $$$\operatorname{lcm}(1,p_1) + \operatorname{lcm}(2, p_2) + \ldots + \operatorname{lcm}(n, p_n)$$$。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

2
1
2

输出 #1

1 
2 1

注意

对于$$$n = 1$$$,只有一种排列,所以答案是$$$[1]$$$。

对于 $$$n = 2$$$,有两种排列:

- $$$[1, 2]$$$ — 总和为 $$$\operatorname{lcm}(1,1) + \operatorname{lcm}(2, 2) = 1 + 2 = 3$$$。
- $$$[2, 1]$$$ — 总和为 $$$\operatorname{lcm}(1,2) + \operatorname{lcm}(2, 1) = 2 + 2 = 4$$$。