Welcome to ZOJ
Select Problem
ZOJ Problem Set - 4133
To the Park

Time Limit: 1 Second      Memory Limit: 65536 KB      Special Judge

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!

Sample Input


Sample Output

1 2 4
2 2 4 3 6

Author: CHEN, Jingbang
Source: The 2019 ICPC China Shaanxi Provincial Programming Contest
Submit    Status