#C. 层岩巨渊中的最长环

传统题

1000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

众所周知，层岩巨渊是一坨奇奇怪怪的环……

钟离说，层岩巨渊的设计参考了以下方案——

对于给定一个特殊的 $n$ 节点无向图：

节点编号依次为 $1,2,\ldots, n$ ；
$\forall 1 \leq i < j \leq n$ ，编号为 $i$ 与编号为 $j$ 的点之间存在一条无向边，当且仅当 $\gcd(i, j) > 1$ 。

对于指定的特殊的 $n$ 节点无向图，你需要构造出一个尽可能长的简单环，即给出节点序列 $a_1,a_2,\ldots,a_m$ ，满足 $(a_1,a_2),(a_2,a_3),\ldots,(a_m,a_1)$ 共 $m$ 个点对之间存在直接相连的边。

第一行一个正整数 $T$ 表示测试组数。

接下来 $T$ 行，每行一个正整数 $n$ 表示该组测试数据的图节点个数。

第一行一个非负整数 $m$ 表示你找到的环大小。

第二行 $m$ 个整数表示你找到的环的节点序列 $a_1,a_2,\ldots,a_m$ 。若存在多种解，输出任意一种即可。

【样例解释】

$n=8$ 时的图长这样：

$n=6$ 或者 $n=7$ 时只需将上图中的 $8$ 和 $7$ 删去即可。

【数据范围】

本题共有 $10$ 个测试点。

Subtasks	Testcases	$T\leq$	$n$
$01$	$1$	$5$	$\leq 10$
$2$	$2$		$\leq 24$
$2$	$3$		$\leq 24$
$3$	$4$		$\leq 300$
$3$	$5$		$\leq 300$
$4$	$6$		$\leq 5000$
$4$	$7$		$\leq 5000$
$5$	$8$	$1$	$= 456789$
$6$	$9$	$5$	$\leq 5\times 10^5$
$6$	$10$	$5$	$\leq 5\times 10^5$

对于所有子任务：保证 $1 \leq T \leq 5, 1 \leq n \leq 5\times 10^5$ 。