← 返回题目列表

Codeforces · 1701/B

B. 排列

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

回想一下,长度 $$$n$$$ 的排列是一个数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个元素恰好出现一次。

对于固定正整数 $$$d$$$,我们将长度为 $$$n$$$ 的排列 $$$p$$$ 的成本定义为索引数 $$$i$$$ $$$(1 \le i < n)$$$,使得 $$$p_i \cdot d = p_{i + 1}$$$。

例如,如果 $$$d = 3$$$ 且 $$$p = [5, 2, 6, 7, 1, 3, 4]$$$,则这种排列的成本为 $$$2$$$,因为 $$$p_2 \cdot 3 = p_3$$$ 且 $$$p_5 \cdot 3 = p_6$$$。

您的任务如下:对于给定值 $$$n$$$,找到长度 $$$n$$$ 的排列和具有最大可能成本的值 $$$d$$$(在选择排列和 $$$d$$$ 的所有方法中)。如果有多个答案,则打印其中任何一个。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) - 测试用例的数量。

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

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在第一行中打印值 $$$d$$$,在第二行中打印 $$$n$$$ 整数 - 排列本身。如果有多个答案,则打印其中任何一个。

示例

输入 #1

2
2
3

输出 #1

2
1 2
3
2 1 3