每个人都喜欢素数。爱丽丝是一个人,因此她也分享对他们的爱。鲍勃想送她一份深情的礼物,但想不出什么有创意的礼物。因此,他会给她一张图表。多么原创啊,鲍勃!爱丽丝一定会很兴奋!
在构建图表时,他需要满足四个条件:
- 它必须是一个简单的无向图,即没有多个(平行)边和自循环。
- 顶点数必须恰好为 $$$n$$$ — 他选择的数字。这个数不一定是素数。
- 边的总数必须是质数。
- 每个顶点的度数(即连接到顶点的边数)必须是素数。
下面是 $$$n = 4$$$ 的示例。第一张图(左图)无效,因为顶点 $$$2$$$ (和 $$$4$$$)的度数等于 $$$1$$$,这不是素数。第二张图(中间一张)无效,因为边的总数为 $$$4$$$,这不是素数。第三张图(右图)是 $$$n = 4$$$ 的有效答案。
请注意,该图可以断开连接。
请帮助鲍勃找到任何这样的图!
输入
输入由单个整数 $$$n$$$ ($$$3 \leq n \leq 1\,000$$$) 组成 - 顶点数。
输出
如果没有满足条件的图形,则打印包含整数 $$$-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$$$ 之间有一条边。每个顶点的度数必须是素数。不得有多个(平行)边或自环。
如果有多个解决方案,您可以打印其中任何一个。
请注意,该图可以断开连接。
示例
输入 #1
4
输出 #1
5 1 2 1 3 2 3 2 4 3 4
输入 #2
8
输出 #2
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
注意
声明中描述了第一个示例。
在第二个示例中,顶点的度数为 $$$[7, 5, 2, 2, 3, 2, 2, 3]$$$。这些数字中的每一个都是质数。此外,边的数量 $$$13$$$ 也是素数,因此两个条件都满足。