{"problem":{"name":"[SNCPC2019] To the Park","description":{"content":"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 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9647"},"statements":[{"statement_type":"Markdown","content":"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.\n\nFor 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.\n\nPlease help DreamGrid form as many groups as possible.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\n\nThe first and only line contains an integer $n$ ($1 \\le n \\le 10^5$), indicating the number of students.\n\nIt's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.\n\n## Output\n\nFor 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.\n\nPlease, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9647","tags":["2019","Special Judge","O2优化","陕西","素数判断,质数,筛法","省赛/邀请赛"],"sample_group":[["3\n1\n4\n6\n","0\n1 2 4\n2 2 4 3 6\n"]],"created_at":"2026-03-03 11:09:25"}}