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.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;

public class B {
    static long mod=(long)1e9+7;
    static long mod1=998244353;

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);


        int t= 1;
        while(t-->0) {

            int n=in.nextInt();

            int k=n/2+1;
            out.println(k);

            for(int i=1;i<=n/2+n%2;i++)
                out.println(1+" "+i);

            int x=n/2+n%2+1;
            int z=2;
            while(x<=n){
                out.println(k+" "+z++);
                x++;
            }

        }
        out.close();
    }




    static final Random random=new Random();

    static void ruffleSort(int[] a) {
        int n=a.length;//shuffle, then sort
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n), temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }
    static long gcd(long x, long y){
        if(x==0)
            return y;
        if(y==0)
            return x;
        long r=0, a, b;
        a = Math.max(x, y);
        b = Math.min(x, y);
        r = b;
        while(a % b != 0){
            r = a % b;
            a = b;
            b = r;
        }
        return r;
    }
    static long modulo(long a,long b,long c){
        long x=1,y=a%c;
        while(b > 0){
            if(b%2 == 1)
                x=(x*y)%c;
            y = (y*y)%c;
            b = b>>1;
        }
        return  x%c;
    }
    public static void debug(Object... o){
        System.err.println(Arrays.deepToString(o));
    }

    static int upper_bound(int[] arr,int n,int x){
        int mid;
        int low=0;
        int high=n;
        while(low<high){
            mid=low+(high-low)/2;
            if(x>=arr[mid])
                low=mid+1;
            else
                high=mid;
        }
        return low;
    }

    static int lower_bound(int[] arr,int n,int x){
        int mid;
        int low=0;
        int high=n;
        while(low<high){
            mid=low+(high-low)/2;
            if(x<=arr[mid])
                high=mid;
            else
                low=mid+1;
        }
        return low;
    }
    static String printPrecision(double d){
        DecimalFormat ft = new DecimalFormat("0.00000000000");
        return String.valueOf(ft.format(d));
    }
    static int countBit(long mask){
        int ans=0;
        while(mask!=0){
            mask&=(mask-1);
            ans++;
        }
        return ans;
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
        public int[] readArray(int n)
        {
            int[] arr=new int[n];
            for(int i=0;i<n;i++) arr[i]=nextInt();
            return arr;
        }
    }
}