Prime Graph

Description:

Input:

The input consists of a single integer $$$n$$$ ($$$3 \leq n \leq 1\,000$$$) — the number of vertices.

Output:

If there is no graph satisfying the conditions, print a single line containing the integer $$$-1$$$.

Otherwise, first print a line containing a prime number $$$m$$$ ($$$2 \leq m \leq \frac{n(n-1)}{2}$$$) — the number of edges in the graph. Then, print $$$m$$$ lines, the $$$i$$$-th of which containing two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — meaning that there is an edge between vertices $$$u_i$$$ and $$$v_i$$$. The degree of each vertex must be prime. There must be no multiple (parallel) edges or self-loops.

If there are multiple solutions, you may print any of them.

Note that the graph can be disconnected.

Sample Input:

4

Sample Output:

5
1 2
1 3
2 3
2 4
3 4

Sample Input:

8

Sample Output:

13
1 2
1 3
2 3
1 4
2 4
1 5
2 5
1 6
2 6
1 7
1 8
5 8
7 8

Note:

The first example was described in the statement.

In the second example, the degrees of vertices are $$$[7, 5, 2, 2, 3, 2, 2, 3]$$$. Each of these numbers is prime. Additionally, the number of edges, $$$13$$$, is also a prime number, hence both conditions are satisfied.