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.*;
import java.math.*;
public class temp
{
    static FastReader s;;
    static class pair
    {
        int a,b;
        pair(int x, int y)
        {
            a=x;
            b=y;
        }
    }
    public static void main(String[] args) throws IOException
    {
        
        s = new FastReader();
        int n = s.ni();
        int m = (int)Math.ceil((n+1)/2.0);
        println(m);
        for (int i = 0; i < m; i++)
        {
            println("1 "+(i+1));
        }
     
        for (int i = 0; i < (n-m); i++)
        {
            println((i+2)+" "+m);
        }
    }   
    
    
    
   /*

    ********if input in hashmap*********

    for (int i = 0; i < n; i++)
    {
        int x = s.ni();
        if (!hm.containsKey(x))
            hm.put(x, 1);
        else
            hm.put(x, hm.get(x) + 1);
    }

     */
 /*

    ********if input in 2darray*********

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            arr[i][j] = s.ni();
        }
    }

     */
 /*
    
    *********GCD**********

    private static int gcdThing(int a, int b)
    {
        return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).intValue();
    }

     */
 /*

    ***********nCr**********

    static int nCr(int n, int k)
    {
        int ans = 1;
        if ( k > n - k )
            k = n - k;
        for (int i = 0; i < k; ++i)
        {
            ans *= (n - i);
            ans /= (i + 1);
        }
        return res;
    }

     */
 /*
    ******Method to check if x is power of 2********
    
    static boolean isPowerOfTwo (int x)
    {
        return x!=0 && ((x&(x-1)) == 0);
    }
     */
 /*
    *******generate all primes*******
    
    void sieveOfEratosthenes(int n)
    {
        // Create a boolean array "prime[0..n]" and initialize
        // all entries it as true. A value in prime[i] will
        // finally be false if i is Not a prime, else true.
        boolean prime[] = new boolean[n+1];
        for(int i=0;i<n;i++)
            prime[i] = true;

        for(int p = 2; p*p <=n; p++)
        {
            // If prime[p] is not changed, then it is a prime
            if(prime[p] == true)
            {
                // Update all multiples of p
                for(int i = p*2; i <= n; i += p)
                    prime[i] = false;
            }
        }

        // Print all prime numbers
        for(int i = 2; i <= n; i++)
        {
            if(prime[i] == true)
                System.out.print(i + " ");
        }
    }

     */

 /*
    *********permutaion program********

    static boolean shouldSwap(StringBuilder str, int start, int curr)
    {
        for (int i = start; i < curr; i++)
        {
            if (str.charAt(i) == str.charAt(curr))
            {
                return false;
            }
        }
        return true;
    }

    static void findPermutations(StringBuilder str, int index, int n, HashSet<Integer> hs)
    {
        if (index >= n)
        {
            int number = Integer.parseInt(str.toString(), 2);
            hs.add(number);
            return;
        }

        for (int i = index; i < n; i++)
        {

            boolean check = shouldSwap(str, index, i);
            if (check)
            {
                char temp = str.charAt(index);
                str.setCharAt(index, str.charAt(i));
                str.setCharAt(i, temp);
                findPermutations(str, index + 1, n, hs);
                temp = str.charAt(index);
                str.setCharAt(index, str.charAt(i));
                str.setCharAt(i, temp);
            }
        }
    }
     */
 /*
    ********** island program********

    public static int findisland(int[][]a,int n,int m)
    {
        int count = 0;
        int [][]visited = new int[n][m];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (visited[i][j] == 0 && a[i][j] == 1)
                {
                    count++;
                    island(a, n, m, i, j, visited);
                }
            }

        }
        return count;
    }
    static void island(int [][]a, int n, int m,int i, int j, int[][] visited)
    {
        if (i >= 0 && i < n && j >= 0 && j < m && visited[i][j] == 0 && a[i][j] == 1)
        {
            visited[i][j] = 1;
            for (int k = -1; k <= 1; k++)
            {
                for (int l = -1; l <= 1; l++)
                {
                    if (i+k >= 0 && i+k < n && j+l >= 0 && j+l < m )
                        island(a, n, m, i+k, j+l, visited);
                }
            }
        }
        else
            return;
    }

     */


    
    static void println(Object line) 
    {
        System.out.println(line);
    }
    static void print(Object line) 
    {
        System.out.print(line);
    }
    static Integer[] iarr(int n)
    {
        Integer arr[]=new Integer[n];
        for(int i = 0; i < n;i++)
            arr[i]=s.ni();
        return arr;
    }

    static Long[] larr(int n)
    {
        Long arr[]=new Long[n];
        for(int i = 0; i < n;i++)
            arr[i]=s.nl();
        return arr;
    }

    static Integer[][] i2arr(int n, int m)
    {
        Integer arr[][]=new Integer[n][m];
        for(int i = 0; i < n;i++)
            for(int j = 0; j < m;j++)
                arr[i][j]=s.ni();
        return arr;
    }

    static Long[][] l2arr(int n, int m)
    {
        Long arr[][]=new Long[n][m];
        for(int i = 0; i < n;i++)
            for(int j = 0; j < m;j++)
                arr[i][j]=s.nl();
        return arr;
    }
    static class Reader
    {

        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                {
                    break;
                }
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int ni() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
            {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
            {
                c = read();
            }
            do
            {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
            {
                return -ret;
            }
            return ret;
        }

        public long nl() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
            {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
            {
                c = read();
            }
            do
            {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
            {
                return -ret;
            }
            return ret;
        }

        public double nd() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
            {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
            {
                c = read();
            }

            do
            {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
            {
                return -ret;
            }
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
            {
                buffer[0] = -1;
            }
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
            {
                fillBuffer();
            }
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
            {
                return;
            }
            din.close();
        }
    }

    /*recommended*/
    static class FastReader
    {

        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public FastReader(String file_name) throws IOException
        {
            br = new BufferedReader(new FileReader(file_name));
        }
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int ni()
        {
            return Integer.parseInt(next());
        }

        long nl()
        {
            return Long.parseLong(next());
        }

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

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

    }
}