CF1178D.Prime Graph

Every person likes prime numbers. Alice is a person, thus she also shares the love for them. Bob wanted to give her an affectionate gift but couldn't think of anything inventive. Hence, he will be giving her a graph. How original, Bob! Alice will surely be thrilled!

When building the graph, he needs four conditions to be satisfied:

• It must be a simple undirected graph, i.e. without multiple (parallel) edges and self-loops.
• The number of vertices must be exactly $n$ — a number he selected. This number is not necessarily prime.
• The total number of edges must be prime.
• The degree (i.e. the number of edges connected to the vertex) of each vertex must be prime.

Below is an example for $n = 4$. The first graph (left one) is invalid as the degree of vertex $2$ (and $4$) equals to $1$, which is not prime. The second graph (middle one) is invalid as the total number of edges is $4$, which is not a prime number. The third graph (right one) is a valid answer for $n = 4$.

Note that the graph can be disconnected.

Please help Bob to find any such graph!

每个人都喜欢质数。Alice 是一个人，因此她也同样热爱质数。Bob 想送她一份充满爱意的礼物，却想不出什么有创意的点子。于是，他决定送她一张图。多么别出心裁啊，Bob！Alice 一定会欣喜若狂！

在构造这张图时，他需满足以下四个条件：

• 它必须是一张简单无向图，即不含多重（平行）边和自环；
• 顶点数必须恰好为 $n$ —— 这是他选定的一个数。该数本身不一定是质数；
• 边的总数必须是质数；
• 每个顶点的度数（即与该顶点相连的边的数量）必须是质数。

下图是一个 $n = 4$ 的示例：第一张图（左侧）无效，因为顶点 $2$（以及顶点 $4$）的度数为 $1$，而 $1$ 不是质数；第二张图（中间）无效，因为总边数为 $4$，而 $4$ 不是质数；第三张图（右侧）是 $n = 4$ 的一个合法解。

注意：该图可以是非连通的。

请帮 Bob 构造出任意一张满足上述条件的图！

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

输入包含一个整数 $n$（$3 \leq n \leq 1\,000$）——顶点的数量。

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.

如果不存在满足条件的图，则输出一行，包含整数 $-1$。

否则，首先输出一行，包含一个质数 $m$（$2 \leq m \leq \frac{n(n-1)}{2}$）——表示图中的边数。然后输出 $m$ 行，其中第 $i$ 行包含两个整数 $u_i$、$v_i$（$1 \leq u_i, v_i \leq n$），表示顶点 $u_i$ 与 $v_i$ 之间存在一条边。每个顶点的度数必须为质数。图中不能存在重边（平行边）或自环。

若存在多个解，可输出任意一个。

注意：该图可以是非连通的。

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.

第一个示例已在题目描述中给出。

在第二个示例中，各顶点的度数为 $[7, 5, 2, 2, 3, 2, 2, 3]$。其中每个数均为素数。此外，边的数量 $13$ 也是一个素数，因此两个条件均满足。