题目描述

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

对于一个固定的正整数 $d$，我们定义长度为 $n$ 的排列 $p$ 的代价为满足 $p_i \cdot d = p_{i + 1}$ 的下标 $i$ 的个数（$1 \le i < n$）。

例如，如果 $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$ 个整数，表示排列本身。如果有多组答案，输出任意一组即可。

说明/提示

由 ChatGPT 4.1 翻译

样例

2
2
3

2
1 2
3
2 1 3