{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"Gugug wants to build a prime graph.\n\nIn order to build a prime graph, he needs four conditions to be satisfied:\n\n- The graph must be a simple undirected graph, i.e. without multiple (parallel) edges and self-loops.\n- The number of vertices must be exactly $n$ — a number he has selected before.\n- The total number of edges must be prime. (But $n$ is not necessarily prime!)\n- The degree (i.e. the number of edges connected to the vertex) of each vertex must be prime.\n\n+ The graph can be disconnected or connected.\n\nPlease help Gugug to build a prime graph!\n\n---\n\nBelow is an example for $n\u003d4$. \n\nThe first graph (left one) is invalid as the degree of vertex $2$ (and $4$) equals to $1$, which is not prime number.\n\nThe second graph (middle one) is invalid as the total number of edges is $4$, which is not a prime number. \n\nThe third graph (right one) is a valid answer for $n\u003d4$.\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" SRC\u003d\"CDN_BASE_URL/8e20a7976e3d19626cd9773fe7d8c790?v\u003d1564998163\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \n\u003c/center\u003e\n\u003cp\u003eNote that the graph can be disconnected.\u003c/p\u003e"}},{"title":"Input","value":{"format":"MD","content":"The input consists of a single integer n (3≤n≤1000) — the number of vertices."}},{"title":"Output","value":{"format":"MD","content":"If there is no graph satisfying the conditions, print a single line containing the integer $−1$.\n\nOtherwise, \n\n+ First print a line containing a prime number m (2≤m≤ n(n−1)/2) — the number of edges in the graph. \n+ Then, print $m$ lines, the $i$-th of which containing two integers $u_i$, $v_i$ $(1≤u_i,v_i≤n)$ — meaning that there is an edge between vertices $u_i$ and $v_i$. \n+ The degree of each vertex must be prime. There must be no multiple (parallel) edges or self-loops.\n\nIf there are multiple solutions, you may print any of them."}},{"title":"Examples","value":{"format":"MD","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e4\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e5\n1 2\n1 3\n2 3\n2 4\n3 4\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e8\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e13\n1 2\n1 3\n2 3\n1 4\n2 4\n1 5\n2 5\n1 6\n2 6\n1 7\n1 8\n5 8\n7 8\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"MD","content":"\u003cp\u003eThe first example was described in the statement.\u003c/p\u003e\n\u003cp\u003eIn 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.\u003c/p\u003e\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" SRC\u003d\"CDN_BASE_URL/dfab2bd6627507bda9aaf8342b422d9c?v\u003d1564998163\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \n\u003c/center\u003e"}}]}