P15014 构造奶龙

你说得对，但是 ::::info[七彩奶龙]  ::::

你有 $n$ 只奶龙玩偶，编号分别从 $1 \sim n$。 一天，你以一个奇怪的顺序使 $n$ 只奶龙排成一排，你惊奇地发现，每对相邻的奶龙可以给你带来奶龙值。 具体地，两只相邻的编号分别为 $i,j$ 的奶龙可以给你带来 $\sum_{q \in \mathbb{P}}[q|\operatorname{lcm}(i,j)]$ （即 $\operatorname{lcm}(i,j)$ 的质因数分解中**不同的**质因子数量，$\mathbb{P}$ 指质数集）的奶龙值，一个方案的总奶龙值是每对相邻的奶龙给你带来的奶龙值中的最大值。 你不希望总奶龙值太大，所以你希望以一种顺序排列奶龙，最小化总奶龙值。 如果你成功把奶龙玩偶排成总奶龙值最小的的情况，它们就会变成七彩奶龙并让你通过这个题。 ### 形式化题意 定义奶龙值函数 $f(i,j)=\sum_{q \in \mathbb{P}}[q|\operatorname{lcm}(i,j)]$，其中 $\mathbb{P}$ 指质数集。 定义值域为 $1 \sim n$ 的长为 $n$ 的排列 $p$ 的总奶龙值 $g(p)=\max_{i=1}^{n-1}f(p_i,p_{i+1})$。 构造长为 $n$ 的排列 $p$，使得 $p$ 在所有排列中总奶龙值最小，即不存在一个值域为 $1 \sim n$ 的长为 $n$ 的排列 $q$ 满足 $g(q)

共 $T+1$ 行。 第一行一个正整数 $T$。 以下 $T$ 行每行一个数 $n$，表示一组数据。

对于每组数据，输出两行。 第一行一个数 $ans$ 表示最小的奶龙值，你需要保证 $0 \leq ans \leq n$。 第二行 $n$ 个数表示奶龙的排列方案 $p$，**你需要保证这是一个合法排列**。

### 样例解释 对于 $n=3$，除 $p=[2,1,3]$ 外，$p=[3,1,2]$ 也是可接受的答案，这两个排列的总奶龙值均为 $1$，容易证明在 $n=3$ 时这是可能的最小总奶龙值。 ### 评分方式 在一个测试点中只有 $ans$ 与 $p$ 均正确，才可以获得 $100\%$ 的分数，否则不能获得分数。 ### 数据范围 | Subtask | points | $1 \leq n\leq$ | | :-----------: | :-----------: | :-----------: | | 1 | 10 | $22$ | | 2 | 10 | $30$ | | 3 | 10 | $40$| | 4 | 10 | $100$ | | 5 | 10 | $1000$ | | 6 | 10 | $10^4$| | 7 | 10 | $5 \times 10^4$| | 8 | 10 | $10^5$| | 9 | 10 | $2 \times 10^5$| | 10 | 10 | $10^6$| 对于所有数据，保证 $1 \leq T \leq 100$，且 $1 \leq \sum n \leq 3 \times 10^6$。 另外，对于 $n \leq 100$ 及以下的子任务（即 $1 \sim 4$ 号子任务），保证测试点中的第 $i$ 组数据满足 $n=i$。