Maximum Grouping of Students

BaoBao and his n-1 classmates are going to the park. Their teacher, DreamGrid, assigns each student a unique index from 1 to \(n\). DreamGrid wants to form groups; each group must consist of exactly two students, and the two indices in each group must share a common divisor greater than 1 (i.e. for students with indices \(i\) and \(j\), it is required that \(\gcd(i,j) > 1\)). Note that each student can be in at most one group and it is not necessary to group every student.

Your task is to help DreamGrid form as many valid groups as possible.

Input Constraints: \(2 \le n \le \text{small}\) (the test data will be such that a \(O(n^2)\) solution is sufficient).

inputFormat

The input consists of a single integer \(n\) which represents the number of students. The students are numbered from 1 to \(n\).

outputFormat

On the first line, output an integer denoting the maximum number of groups (pairs) that can be formed. Then output that many lines; each line contains two integers \(a\) and \(b\) (\(a < b\)) representing the indices of the two students in one valid group. If there are multiple answers, any one is accepted.

sample

6

2
2 4
3 6