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:

/*
9 2
        1 1 1 1 1 0 0 0 0
        1 2
        1 5
        5 6
        5 7
        2 3
        2 4
        3 8
        3 9
*/


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Question{


    static LinkedList<Integer> adj[] ;
    static boolean[] visited;
    static boolean[] visited_;
    static int[] ans;
    static int count_ = 0;
    static final int MAX_SIZE = 1000001;
    static Vector<Boolean>isprime = new Vector<>(MAX_SIZE);
    static Vector<Integer>prime = new Vector<>();
    static Vector<Integer>SPF = new Vector<>(MAX_SIZE);
    public static  void main(String[] args) throws IOException {
        Reader.init(System.in);
        int n = Reader.nextInt();
        int m  = 0;
        if (n%2==1){
            m = (n/2)+1;
            System.out.println(m);
            for (int i = 0 ; i < m ; i++){
                System.out.println(1 + " " + (i+1));
            }
            for (int i = 0 ; i < m - 1 ; i++){
                System.out.println(m + " " +(i+2));
            }
        }
        else{

            m = (n/2)+1;
            System.out.println(m);
            for (int i = 0 ; i < n/2 ; i++){
                System.out.println(1 + " " +(i+1));
            }
            for (int i = 0 ; i < n /2; i++) {
                System.out.println(m + " " + (i+1));
            }
        }






















}
    static void printArr(int[] arr){
        for (int i = 0 ; i < arr.length ; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    static void printArr(long[] arr){
        for (int i = 0 ; i < arr.length ; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    static void manipulated_seive(int N)
    {
        // 0 and 1 are not prime
        isprime.set(0, false);
        isprime.set(1, false);

        // Fill rest of the entries
        for (int i=2; i<N ; i++)
        {
            // If isPrime[i] == True then i is
            // prime number
            if (isprime.get(i))
            {
                // put i into prime[] vector
                prime.add(i);

                // A prime number is its own smallest
                // prime factor
                SPF.set(i,i);
            }

            // Remove all multiples of  i*prime[j] which are
            // not prime by making isPrime[i*prime[j]] = false
            // and put smallest prime factor of i*Prime[j] as prime[j]
            // [for exp :let  i = 5, j = 0, prime[j] = 2 [ i*prime[j] = 10]
            // so smallest prime factor of '10' is '2' that is prime[j] ]
            // this loop run only one time for number which are not prime
            for (int j=0;
                 j < prime.size() &&
                         i*prime.get(j) < N && prime.get(j) <= SPF.get(i);
                 j++)
            {
                isprime.set(i*prime.get(j),false);

                // put smallest prime factor of i*prime[j]
                SPF.set(i*prime.get(j),prime.get(j)) ;
            }
        }
    }
    static int countGreater(long arr[], int n, long k)
    {
        int l = 0;
        int r = n - 1;

        // Stores the index of the left most element
        // from the array which is greater than k
        int leftGreater = n;

        // Finds number of elements greater than k
        while (l <= r) {
            int m = l + (r - l) / 2;

            // If mid element is greater than
            // k update leftGreater and r
            if (arr[m] > k) {
                leftGreater = m;
                r = m - 1;
            }

            // If mid element is less than
            // or equal to k update l
            else
                l = m + 1;
        }

        // Return the count of elements greater than k
        return (n - leftGreater);
    }

    static void sortbyColumn(int arr[][], int col)
    {
        // Using built-in sort function Arrays.sort
        Arrays.sort(arr, new Comparator<int[]>() {

            @Override
            // Compare values according to columns
            public int compare(final int[] entry1,
                               final int[] entry2) {

                // To sort in descending order revert
                // the '>' Operator
                if (entry1[col] > entry2[col])
                    return 1;
                else
                    return -1;
            }
        });  // End of function call sort().
    }
    static int binarySearchCount(long arr[], int n, long key,int left)
    {
        int right = n;

        int mid = 0;
        while (left < right) {
            mid = (right + left) >> 1;

            // Check if key is present in array
            if (arr[mid] == key) {

                // If duplicates are present it returns
                // the position of last element
                while (mid+1<n && arr[mid + 1] == key)
                    mid++;
                break;
            }

            // If key is smaller, ignore right half
            else if (arr[mid] > key)
                right = mid;

                // If key is greater, ignore left half
            else
                left = mid + 1;
        }

        // If key is not found in array then it will be
        // before mid
        while (mid > - 1 && arr[mid] > key)
            mid--;

        // Return mid + 1 because of 0-based indexing
        // of array
        return mid + 1;
    }

    static long gcd(long a, long b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);

    }

    // method to return LCM of two numbers
    static long lcm(long a, long b)
    {
        return (a*b)/gcd(a, b);
    }

    static long fun(long n){
        long max = -1;
        for (int i = 0 ; i < n ; i++){
            String x = Integer.toString(i);
            long product = 1;
            for (int j = 0 ; j < x.length() ; j++){
                product = product * Long.parseLong(Character.toString(x.charAt(j)));
            }
            max = Math.max(product,max);
        }
        return max;
    }

    public static void print2D(int mat[][])
    {
        // Loop through all rows
        for (int[] row : mat)

            // converting each row as string
            // and then printing in a separate line
            System.out.println(Arrays.toString(row));
    }




}



class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }

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

class MergeSort {
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    void merge(int arr[], int l, int m, int r) {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int L[] = new int[n1];
        int R[] = new int[n2];

        /*Copy data to temp arrays*/
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    void sort(int arr[], int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = (l + r) / 2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr, m + 1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    static long phi(long n,long R)
    {

        long result = R;


        for (long p = 2; p * p <= n; ++p)
        {


            if (n % p == 0)
            {


                while (n % p == 0)
                    n =n/p;
                result =result - ( result / p);
            }
        }


        //System.out.println("n" + n);
        if (n > 1)
            result -= result / n;
        return result;
    }
}

class person{
    int index;
    int money;

    public person(int index, int money) {
        this.index = index;
        this.money = money;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    public void setMoney(int money) {
        this.money = money;
    }

    public int getIndex() {
        return index;
    }

    public int getMoney() {
        return money;
    }
}

class StudentComparator implements Comparator<person>{

    // Overriding compare()method of Comparator
    // for descending order of cgpa
    public int compare(person s1, person s2) {
        if (s1.money > s2.money)
            return 1;
        else if (s1.money < s2.money) {
            return -1;
        }
        else{
            if (s1.index >s2.index){
                return 1;
            }
            else{
                return -1;
            }
        }

    }
}


class SegementTree{
    int size;
    long[] tree;

    long update(int index, int left , int right,int i , int x){
        if (i< left || i>right){
            return tree[x];
        }
        if (left==right){
            tree[index] = x;
        }
        int s = (left + right)/2;
        update(index*2 + 1,left,s, i,x);
        update(index*2 + 1,s+1,right, i,x);
        tree[index] = tree[index*2 + 1] + tree[index*2+1];
        return tree[index];
    }

    public SegementTree(int size) {
        this.size = size;
    }

    public SegementTree(int size, long[] tree) {
        this.size = size;
        this.tree = tree;
    }
}