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.util.*;
 
 
 
import java.awt.Point;
import java.math.*;
import java.io.*;
@SuppressWarnings("unused")
public class abc {int[] b;	String g="";int c=0;int modu=1000000000+7;ArrayList<Integer> list=new ArrayList<Integer>();String s;int[] size;int[] id;
int[]ab;int[] data;int mod=100000;LinkedList<Integer> queue=new LinkedList<Integer>();int dis=0;int max=0;ArrayList<Integer>[] arr;static int MAX = 1000001; 
static int factor[];long glo;int f;int gl;int[] rem;int[] vis;int[] a;int n;int k;
int[] rank;int[] par;long[] facto;
	public static void main(String[] args)  {
                new abc().solve();
                                  }
	
            public void solve(){
            	double n=sc.nextInt();
            	if(n==1) {
            		System.out.println(1);
            		System.out.println("1 1");
            	}
            	else {
            		System.out.println((int)(Math.ceil((n-1)/2+1)));
            		int y=(int)n;
            		y--;
            		System.out.println("1 1");
            		int r=1,c=1;int h=0;
            		while(y--!=0) {
            			if(h==0) {
            				c+=1;
            				h=1;
            			}
            			else {
            				r+=1;
            				h=0;
            			}
            			System.out.println(r+" "+c);
            			
            		}
            	}
            	
                }
           
          void factorial() {
        	  facto[0]=1;
        	  for(int i=1;i<=1000;i++) {
        		  facto[i]=(facto[i-1]%modu*i%modu)%modu;
        	  }
          }
           
           
            public class Node{
        		int x;long color;int y;
        		Node par;
        		public Node(int a,int b) {
        			x=a;y=b;
        			
        		}
        	}
       				
       				 FastReader sc=new FastReader();
       				 static class FastReader
       				     {
       				         BufferedReader br;
       				         StringTokenizer st;
       				  
       				         public FastReader()
       				         {
       				             br = new BufferedReader(new
       				                      InputStreamReader(System.in));
       				         }
       				  
       				         String next()
       				         {
       				             while (st == null || !st.hasMoreElements())
       				             {
       				                 try
       				                 {
       				                     st = new StringTokenizer(br.readLine());
       				                 }
       				                 catch (IOException  e)
       				                 {
       				                     e.printStackTrace();
       				                 }
       				             }
       				             return st.nextToken();
       				         }
       				  
       				         int nextInt()
       				         {
       				             return Integer.parseInt(next());
       				         }
       				  
       				         long nextLong()
       				         {
       				             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;
       				         }
       				     }}