Problem: You are given an integer n.

You should find a list of pairs (x_1, y_1), (x_2, y_2), ..., (x_q, y_q) (1 ≤ x_i, y_i ≤ n) satisfying the following condition.

Let's consider some function f: N × N → N (we define N as the set of positive integers). In other words, f is a function that returns a positive integer for a pair of positive integers.

Let's make an array a_1, a_2, …, a_n, where a_i = i initially.

You will perform q operations, in i-th of them you will: 

  1. assign t = f(a_{x_i}, a_{y_i}) (t is a temporary variable, it is used only for the next two assignments); 
  2. assign a_{x_i} = t; 
  3. assign a_{y_i} = t. 



In other words, you need to simultaneously change a_{x_i} and a_{y_i} to f(a_{x_i}, a_{y_i}). Note that during this process f(p, q) is always the same for a fixed pair of p and q.

In the end, there should be at most two different numbers in the array a.

It should be true for any function f.

Find any possible list of pairs. The number of pairs should not exceed 5 ⋅ 10^5.

Input

The single line contains a single integer n (1 ≤ n ≤ 15 000).

Output

In the first line print q (0 ≤ q ≤ 5 ⋅ 10^5) — the number of pairs.

In each of the next q lines print two integers. In the i-th line print x_i, y_i (1 ≤ x_i, y_i ≤ n).

The condition described in the statement should be satisfied.

If there exists multiple answers you can print any of them.

Examples

Input


3


Output


1
1 2


Input


4


Output


2
1 2
3 4

Note

In the first example, after performing the only operation the array a will be [f(a_1, a_2), f(a_1, a_2), a_3]. It will always have at most two different numbers.

In the second example, after performing two operations the array a will be [f(a_1, a_2), f(a_1, a_2), f(a_3, a_4), f(a_3, a_4)]. It will always have at most two different numbers.

Solution (in JAVA):

Solution:
import sun.security.krb5.internal.PAData;

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        MyReader reader = new MyReader(System.in);
//        MyReader reader = new MyReader(new FileInputStream("input.txt"));
        MyWriter writer = new MyWriter(System.out);
        new Main().run(reader, writer);
        writer.close();
    }

    private void run(MyReader reader, MyWriter writer) throws Exception {
        int n = reader.nextInt();
        int a = 2;
        while (a < n) {
            a *= 2;
        }
        a /= 2;
        int step = 1;
        List<Pair<Integer>> list1 = new ArrayList<>();
        List<Pair<Integer>> list2 = new ArrayList<>();
        while (step < a) {
            int i = 0;
            for (int j = 0; j < a; j += step * 2) {
                for (int k = 0; k < step; k++) {
                    list1.add(new Pair<>(j + k, j + k + step));
                    list2.add(new Pair<>(n - a + j + k, n - a + j + k + step));
                }
            }
            step *= 2;
        }
        list1.addAll(list2);
        writer.println(list1.size());
        for (Pair<Integer> integerPair : list1) {
            writer.println((integerPair.x + 1) + " " + (integerPair.y + 1));
        }
    }

    class Pair<T> extends Pair2<T, T> {

        public Pair(T x, T y) {
            super(x, y);
        }
    }

    class Pair2<T, U> {

        T x;
        U y;

        public Pair2(T x, U y) {
            this.x = x;
            this.y = y;
        }
    }

    public class DSU {

        int n;
        int[] p;
        int[] r;

        DSU(int n) {
            this.n = n;
            p = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = i;
            }
            r = new int[n];
        }

        int get(int x) {
            if (p[x] != x) {
                p[x] = get(p[x]);
            }
            return p[x];
        }

        void union(int x, int y) {
            x = get(x);
            y = get(y);
            if (x == y) {
                return;
            }
            if (r[x] == r[y]) {
                r[x]++;
            }
            if (r[x] < r[y]) {
                p[x] = y;
            } else {
                p[y] = x;
            }
        }
    }

    public class Graph<T> {

        int counter = 0;
        List<Node> nodes = new ArrayList<>();
        List<Long> dist;

        void initNodes(int n) {
            for (int i = 0; i < n; i++) {
                nodes.add(new Node());
            }
        }

        void addNode(T obj) {
            nodes.add(new Node(obj));
        }

        void addEdge(int i, int j, boolean oriented) {
            addEdge(i, j, 0, oriented);
        }

        void addEdge(int i, int j, long w, boolean oriented) {
            Node from = nodes.get(i);
            Node to = nodes.get(j);
            addEdge(from, to, w, oriented);
        }

        void addEdge(Node from, Node to, boolean oriented) {
            addEdge(from, to, 0, oriented);
        }

        void addEdge(Node from, Node to, long w, boolean oriented) {
            Edge edge = new Edge(from, to, w);
            from.edges.add(edge);
            if (!oriented) {
                Edge rev = new Edge(to, from, w);
                to.edges.add(rev);
            }
        }

        long mst() {
            List<Edge> list = new ArrayList<>();
            for (Node node : nodes) {
                list.addAll(node.edges);
            }
            list.sort((e1, e2) -> (int) (e1.w - e2.w));
            DSU dsu = new DSU(nodes.size());
            long weight = 0;
            for (Edge edge : list) {
                if (dsu.get(edge.from.i) != dsu.get(edge.to.i)) {
                    weight += edge.w;
                    dsu.union(edge.from.i, edge.to.i);
                }
            }
            return weight;
        }

//    void dijkstra() {
//        PriorityQueue<Main.Pair2<Node, Long>> queue = new PriorityQueue<>((o1, o2) -> (int) (o1.y - o2.y));
//        queue.add(new Main.Pair2<>(nodes.get(0), 0L));
//        while (!queue.isEmpty()) {
//            Main.Pair2<Node, Long> p = queue.poll();
//            Node n = p.x;
//            long d = p.y;
//            if (n.dist != -1) {
//                continue;
//            }
//            n.dist = d;
//            for (Edge edge : n.edges) {
//                queue.add(new Main.Pair2<>(edge.to, d + edge.w));
//            }
//        }
//    }

        class Node {

            int i;
            T obj;
            List<Edge> edges = new ArrayList<>();
            long dist = -1;

            public Node() {
                this(null);
            }

            public Node(T obj) {
                this.i = counter++;
                this.obj = obj;
            }
        }

        class Edge {

            long w;
            Node from;
            Node to;

            public Edge(Node from, Node to) {
                this(from, to, 0);
            }

            public Edge(Node from, Node to, long w) {
                this.from = from;
                this.to = to;
                this.w = w;
            }
        }
    }


    public static class MyReader {

        final BufferedInputStream in;
        final int bufSize = 1 << 16;
        final byte[] buf = new byte[bufSize];
        int i = bufSize;
        int k = bufSize;
        boolean end = false;
        final StringBuilder str = new StringBuilder();

        MyReader(InputStream in) {
            this.in = new BufferedInputStream(in, bufSize);
        }

        int nextInt() throws IOException {
            return (int) nextLong();
        }

        int[] nextIntArray(int n) throws IOException {
            int[] m = new int[n];
            for (int i = 0; i < n; i++) {
                m[i] = nextInt();
            }
            return m;
        }

        int[][] nextIntMatrix(int n, int m) throws IOException {
            int[][] a = new int[n][0];
            for (int j = 0; j < n; j++) {
                a[j] = nextIntArray(m);
            }
            return a;
        }

        long nextLong() throws IOException {
            int c;
            long x = 0;
            int sign = 1;
            while ((c = nextChar()) <= 32) ;
            if (c == '-') {
                sign = -1;
                c = nextChar();
            }
            if (c == '+') {
                c = nextChar();
            }
            while (c >= '0') {
                x = x * 10 + (c - '0');
                c = nextChar();
            }
            return sign * x;
        }

        long[] nextLongArray(int n) throws IOException {
            long[] m = new long[n];
            for (int i = 0; i < n; i++) {
                m[i] = nextLong();
            }
            return m;
        }

        int nextChar() throws IOException {
            if (i == k) {
                k = in.read(buf, 0, bufSize);
                i = 0;
            }
            return i >= k ? -1 : buf[i++];
        }

        String nextString() throws IOException {
            if (end) {
                return null;
            }
            str.setLength(0);
            int c;
            while ((c = nextChar()) <= 32 && c != -1) ;
            if (c == -1) {
                end = true;
                return null;
            }
            while (c > 32) {
                str.append((char) c);
                c = nextChar();
            }
            return str.toString();
        }

        String nextLine() throws IOException {
            if (end) {
                return null;
            }
            str.setLength(0);
            int c = nextChar();
            while (c != '\n' && c != '\r' && c != -1) {
                str.append((char) c);
                c = nextChar();
            }
            if (c == -1) {
                end = true;
                if (str.length() == 0) {
                    return null;
                }
            }
            if (c == '\r') {
                nextChar();
            }
            return str.toString();
        }

        char[] nextCharArray() throws IOException {
            return nextString().toCharArray();
        }

        char[][] nextCharMatrix(int n) throws IOException {
            char[][] a = new char[n][0];
            for (int i = 0; i < n; i++) {
                a[i] = nextCharArray();
            }
            return a;
        }
    }

    public static class MyWriter {

        final BufferedOutputStream out;
        final int bufSize = 1 << 16;
        final byte buf[] = new byte[bufSize];
        int i = 0;
        final byte c[] = new byte[30];
        static final String newLine = System.getProperty("line.separator");

        MyWriter(OutputStream out) {
            this.out = new BufferedOutputStream(out, bufSize);
        }

        void print(long x) throws IOException {
            int j = 0;
            if (i + 30 >= bufSize) {
                flush();
            }
            if (x < 0) {
                buf[i++] = (byte) ('-');
                x = -x;
            }
            do {
                c[j++] = (byte) (x % 10 + '0');
                x /= 10;
            } while (x != 0);
            while (--j >= 0) {
                buf[i++] = c[j];
            }
        }

        void println(long x) throws IOException {
            print(x);
            println();
        }

        void print(int[] m) throws IOException {
            for (int a : m) {
                print(a);
                print(' ');
            }
        }

        void print(long[] m) throws IOException {
            for (long a : m) {
                print(a);
                print(' ');
            }
        }

        void print(String s) throws IOException {
            for (int i = 0; i < s.length(); i++) {
                print(s.charAt(i));
            }
        }

        void print(char x) throws IOException {
            if (i == bufSize) {
                flush();
            }
            buf[i++] = (byte) x;
        }

        void print(char[] m) throws IOException {
            for (char c : m) {
                print(c);
            }
        }

        void println(String s) throws IOException {
            print(s);
            println();
        }

        void println() throws IOException {
            print(newLine);
        }

        void flush() throws IOException {
            out.write(buf, 0, i);
            out.flush();
            i = 0;
        }

        void close() throws IOException {
            flush();
            out.close();
        }
    }
}