1178_D. Prime Graph_32147
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. 

<image>

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 prime. Additionally, the number of edges, 13, is also a prime number, hence both conditions are satisfied.

<image>
import java.util.*;
import java.io.*;

public class DD {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int N = scanner.nextInt();
        ArrayList<Pair> list = new ArrayList<>();
        int cur = N;
        boolean[] sieve = sieve(N *N);
        while(cur <= (N*(N-1))/2) {
            if (sieve[cur]) {
                for(int i = 1; i < N; i++) {
                    list.add(new Pair(i, i + 1));
                }
                list.add(new Pair(1, N));
                int rem = cur - N;
                int p = 1;
                while(rem > 0) {
                    list.add(new Pair(p, p + N/2));
                    p++;
                    rem--;
                }
                break;
            }
            else cur++;
        }
        if (list.size() > 0) {
            out.println(list.size());
            for (Pair pair : list) {
                out.println(pair.a + " " + pair.b);
            }
        }
        else out.println(-1);
        out.flush();
    }
    public static boolean[] sieve(int N) {
        boolean [] a = new boolean[N+1];
        Arrays.fill(a, true);
        a[0] = a[1] = false;
        for (int p = 2; p * p <= N; p++)
            if (a[p]) {
                for (int m = p * p; m <= N; m += p)
                    a[m] = false;
            }
        return a;
    }
    
    static class Pair {
        int a, b;
        public Pair(int aa, int bb) {
            a = aa; b =bb;
        }
    }
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
    }
}
