题目背景
众所周知,层岩巨渊是一坨奇奇怪怪的环……
题目描述
钟离说,层岩巨渊的设计参考了以下方案——
对于给定一个特殊的 n 节点无向图:
- 节点编号依次为 1,2,…,n;
- ∀1≤i<j≤n,编号为 i 与编号为 j 的点之间存在一条无向边,当且仅当 gcd(i,j)>1。
对于指定的特殊的 n 节点无向图,你需要构造出一个尽可能长的简单环,即给出节点序列 a1,a2,…,am,满足 (a1,a2),(a2,a3),…,(am,a1) 共 m 个点对之间存在直接相连的边。
输入格式
第一行一个正整数 T 表示测试组数。
接下来 T 行,每行一个正整数 n 表示该组测试数据的图节点个数。
输出格式
第一行一个非负整数 m 表示你找到的环大小。
第二行 m 个整数表示你找到的环的节点序列 a1,a2,…,am。若存在多种解,输出任意一种即可。
样例 #1
样例输入 #1
3
6
7
8
样例输出 #1
3
2 4 6
3
2 4 6
4
2 4 6 8
提示
【样例解释】
n=8 时的图长这样:
n=6 或者 n=7 时只需将上图中的 8 和 7 删去即可。
【数据范围】
本题共有 10 个测试点。
Subtasks |
Testcases |
T≤ |
n |
01 |
1 |
5 |
≤10 |
2 |
2 |
≤24 |
3 |
3 |
4 |
≤300 |
5 |
4 |
6 |
≤5000 |
7 |
5 |
8 |
1 |
=456789 |
6 |
9 |
5 |
≤5×105 |
10 |
对于所有子任务:保证 1≤T≤5,1≤n≤5×105。