Problem: Nauuo is a girl who loves playing chess.

One day she invented a game by herself which needs n chess pieces to play on a m× m chessboard. The rows and columns are numbered from 1 to m. We denote a cell on the intersection of the r-th row and c-th column as (r,c).

The game's goal is to place n chess pieces numbered from 1 to n on the chessboard, the i-th piece lies on (r_i,\,c_i), while the following rule is satisfied: for all pairs of pieces i and j, |r_i-r_j|+|c_i-c_j|≥|i-j|. Here |x| means the absolute value of x.

However, Nauuo discovered that sometimes she couldn't find a solution because the chessboard was too small.

She wants to find the smallest chessboard on which she can put n pieces according to the rules.

She also wonders how to place the pieces on such a chessboard. Can you help her?

Input

The only line contains a single integer n (1≤ n≤ 1000) — the number of chess pieces for the game.

Output

The first line contains a single integer — the minimum value of m, where m is the length of sides of the suitable chessboard.

The i-th of the next n lines contains two integers r_i and c_i (1≤ r_i,c_i≤ m) — the coordinates of the i-th chess piece.

If there are multiple answers, print any.

Examples

Input


2


Output


2
1 1
1 2

Input


4


Output


3
1 1
1 3
3 1
3 3

Note

In the first example, you can't place the two pieces on a 1×1 chessboard without breaking the rule. But you can place two pieces on a 2×2 chessboard like this:

<image>

In the second example, you can't place four pieces on a 2×2 chessboard without breaking the rule. For example, if you place the pieces like this:

<image>

then |r_1-r_3|+|c_1-c_3|=|1-2|+|1-1|=1, |1-3|=2, 1<2; and |r_1-r_4|+|c_1-c_4|=|1-2|+|1-2|=2, |1-4|=3, 2<3. It doesn't satisfy the rule.

However, on a 3×3 chessboard, you can place four pieces like this:

<image>

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class B {

    private static class Pair<A, B> {
        A a;
        B b;

        Pair(A a, B b) {
            this.a = a;
            this.b = b;
        }

        //    public String getType() { return a.getClass().getSimpleName(); }

        A getA() {
            return a;
        }

        B getB() {
            return b;
        }

        void setA(A a) {
            this.a = a;
        }

        void setB(B b) {
            this.b = b;
        }

        @Override
        public int hashCode() {
            int h1 = a != null ? a.hashCode() : 0;
            int h2 = b != null ? b.hashCode() : 0;
            return 31 * h1 + h2;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Pair)) return false;
            Pair p = (Pair) o;
            return a.equals(p.a) && b.equals(p.b);
        }
    }

    public static void main(String[] args) {
        FastReader in = new FastReader(System.in);
        //        FastReader in2 = new FastReader(new FileInputStream("input.txt"));
        PrintWriter out = new PrintWriter(System.out);
        //        PrintWriter out2 = new PrintWriter(new FileOutputStream("input.txt"));

        int n = in.nextInt();

        List<Pair<Integer, Integer>> list = new ArrayList<>();
        int x = 1, y = 1;
        for (int i = 0; i < n; i++) {
            list.add(new Pair<>(x, y));
            if (x == y)
                x++;
            else
                y++;
        }
        if (x > y)
            x--;

        out.println(x);
        for (Pair p : list)
            out.println(p.getA() + " " + p.getB());



        out.close();
    }

    private static class FastReader {

        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        Integer nextInt() {
            return Integer.parseInt(next());
        }

        Long nextLong() {
            return Long.parseLong(next());
        }

        Double nextDouble() {
            return Double.parseDouble(next());
        }

        String next() {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(nextLine());

            return st.nextToken();
        }

        String nextLine() {
            String x = "";
            try {
                x = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return x;
        }
    }
}