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 javafx.util.Pair; 

public class TaskB_june7 
{ 

/*
 *   ********   *******    ******** 	
 *   *          *    *           *
 *   *          *   *           * 
 *   *          * *            *
 *   *          *   *         *
 *   ********   *    *       *
 */
	static	Reader in=new Reader();
	static Scanner sc=new Scanner(System.in);
	public static void main(String[] args) throws IOException 
	{ 
		double n=in._double();
		int row=(int)Math.ceil((n+1)/2);
		System.out.println(row);
		double count=0;
		for(int i=1;i<=row;i++)
			{	count++;
				System.out.println("1"+" "+i);
			}
		for(int j=2;j<=row;j++) {
			if(count==n)
				System.exit(0);
			System.out.println(j+" "+row);
			count++;
		}
		
	}

 static int partition(Pair<Integer,Integer> arr[], int low, int high) 
    { 
        int pivot = arr[high].getKey();  
        int i = (low-1);
        for (int j=low; j<high; j++) 
        {  
            if (arr[j].getKey() <= pivot) 
            { 
                i++;
                Pair<Integer,Integer> temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
            } 
        }
        Pair<Integer,Integer> temp = arr[i+1]; 
        arr[i+1] = arr[high]; 
        arr[high] = temp; 
  
        return i+1; 
    } 
   static void sort(Pair<Integer,Integer> arr[], int low, int high) 
    { 
        if (low < high) 
        { 
            int pi = partition(arr, low, high); 
            sort(arr, low, pi-1); 
            sort(arr, pi+1, high); 
        } 
    }
	/*
	 * seach algorithm
	 */
	static int return_greater_index(int arr[],int start,int end,int x)
	{
		int ans=-1;
		int mid;
		while(start<=end) {
			 mid=(start+end)/2;
			if(arr[mid]<=x)
				start=mid+1;
			else 
				{
				ans=mid;
				end=mid-1;
				}
		}
		return ans;
	}
public static int lowerBound(int[] a, int v)
	{
		int low = -1, high = a.length;
		while(high-low > 1){
			int h = high+low>>>1;
			if(a[h] >= v){
				high = h;
			}else{
				low = h;
			}
		}
		return high;
	}
static int return_lower_index(int arr[],int start,int end,int x)
	{
		int ans=-1;
		int mid;
		while(start<=end) {
			 mid=(start+end)/2;
			if(arr[mid]<=x) {
				ans=mid;
				start=mid+1;
			}
			else 
				{
				end=mid-1;
				}
		}
		return ans;
	}
	/*
	 * pairs of <int,int> <double,double>
	 */
	static Pair<Integer,Integer> pair(int x,int y){
		Pair<Integer,Integer> p=new Pair<Integer, Integer>(x,y);
		return p;
	}
	static Pair<Double,Double> pair(double x,double y){
		Pair<Double,Double> p=new Pair<Double,Double>(x,y);
		return p;
	}
	/*
	 * for loop
	 */
static void rep(int arr[]) throws IOException {
	int n=arr.length;
	for(int i=0;i<n;i++)
		arr[i]=in.integer();
}
	/*display 
	 array
	 */
	static void display(Integer arr[][],int x,int y) {
		for(int i=0;i<x;i++) {
			for(int j=0;j<y;j++)
			{
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
	}
	static void display(Integer arr[]) {
		int x=arr.length;
			for(int j=0;j<x;j++)
			{
				System.out.print(arr[j]+" ");
			}
			System.out.println();
	}
	
	/*
	 * input 
	 */
	
	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 string() 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 integer() 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 _long() 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 _double() 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(); 
		} 
	} 

}