
ZOJ Problem Set  4133
BaoBao and his $(n1)$ 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. InputThere 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$. OutputFor 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_{2k1}$ 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! Sample Input3 1 4 6 Sample Output0 1 2 4 2 2 4 3 6 Author: CHEN, Jingbang Source: The 2019 ICPC China Shaanxi Provincial Programming Contest 