human
Give me a Python code to find any such graph! given the following:
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!

Input

The input consists of a single integer n (3 ≤ n ≤ 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 ≤ m ≤ (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 ≤ u_i, v_i ≤ 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.

Examples

Input

4

Output

5
1 2
1 3
2 3
2 4
3 4

Input

8

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...
from
assistant
#Here is Python code to find any such graph!
.
__future__ import division, print_function
def main():
    def SieveOfEratosthenes(n): 
        p = 2
        while (p * p <= n): 
              
        # If prime[p] is not changed, then it is a prime 
            if (prime[p] == True): 
              
            # Update all multiples of p 
                for i in range(p * p, n+1, p): 
                    prime[i] = False
            p += 1
            
    
    n=int(input())
    prime = [True for i in range(2*n+3)] 
    SieveOfEratosthenes(2*n+1)
    if n<=2:
        print(-1)
    else :
        if prime[n]:
            print(n)
            print(1,n)
            for i in range(n-1):
                print(i+1,i+2)
        else:
            edges=[]
            edges.append((1,n))
            for i in range(n-1):
                edges.append((i+1,i+2))
            temp=list(range(1,n+1))
            while prime[len(edges)]==False:
                x=temp[-1]
                temp.pop()
                for j in range(len(temp)-1,-1,-1):
                    if temp[j]+1!=x:
                        edges.append((temp[j],x))
                        temp.remove(temp[j])
                        break
            print(len(edges))
            for item in edges:
                print(item[0],item[1])
                        
                
######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or...