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

层岩巨渊中的最长环

题目背景

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

题目描述

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

对于给定一个特殊的 nn 节点无向图:

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

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

输入格式

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

接下来 TT 行,每行一个正整数 nn 表示该组测试数据的图节点个数。

输出格式

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

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

样例 #1

样例输入 #1

3
6
7
8

样例输出 #1

3
2 4 6
3
2 4 6
4
2 4 6 8

提示

【样例解释】

n=8n=8 时的图长这样:

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

【数据范围】

本题共有 1010 个测试点。

Subtasks Testcases TT\leq nn
0101 11 55 10\leq 10
22 22 24\leq 24
33
33 44 300\leq 300
55
44 66 5000\leq 5000
77
55 88 11 =456789= 456789
66 99 55 5×105\leq 5\times 10^5
1010

对于所有子任务:保证 1T5,1n5×1051 \leq T \leq 5, 1 \leq n \leq 5\times 10^5