题目描述

BaoBao and his $(n-1)$ classmates are going to the park. For convenience, their teacher DreamGrid has numbered the students from 1 to $n$ and decides to form the students into some groups, where each group consists of exactly two students.

For some reason, DreamGrid requires that the indices of the two students in the same group should have a common divisor greater than 1. Note that each student can only belong to at most one group, and it's not necessary that every student belongs to a group.

Please help DreamGrid form as many groups as possible.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first and only line contains an integer $n$ ($1 \le n \le 10^5$), indicating the number of students.

It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

输出格式

For each test case output one line. The line first contains an integer $k$ indicating the number of groups, then $2k$ integers $a_1, a_2, \dots, a_{2k}$ follow, indicating that student $a_1$ and $a_2$ belong to the same group, student $a_3$ and $a_4$ belong to the same group, ..., student $a_{2k-1}$ and $a_{2k}$ belong to the same group. The integers in a line are separated by a space. If there are multiple valid answers, you can print any of them.

Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!

题目大意

【题目描述】

宝宝和他的 $(n-1)$ 个同学要去公园。为了方便，他们的老师梦想格子将学生从 1 到 $n$ 编号，并决定将学生分成一些小组，每组恰好由两个学生组成。

由于某种原因，梦想格子要求同组的两个学生的编号必须有一个大于 1 的公约数。注意，每个学生最多只能属于一个小组，并且不需要每个学生都属于一个小组。

请帮助梦想格子组成尽可能多的小组。

【输入格式】

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行且唯一一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示学生的数量。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

【输出格式】

对于每个测试用例，输出一行。该行首先包含一个整数 $k$，表示小组的数量，然后是 $2k$ 个整数 $a_1, a_2, \dots, a_{2k}$，表示学生 $a_1$ 和 $a_2$ 属于同一小组，学生 $a_3$ 和 $a_4$ 属于同一小组，以此类推。行内的整数由空格分隔。如果有多个有效答案，可以输出其中任何一个。

请不要在每行的末尾输出多余的空格，否则你的解决方案可能会被认为不正确！

翻译来自于：ChatGPT。

3
1
4
6

0
1 2 4
2 2 4 3 6