回想一下,长度 $$$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