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.*;
	import java.lang.*;
	import java.util.stream.Collectors;

	import static java.lang.Math.*;
	 
	public class Main implements Runnable
	{
		static class InputReader
		{
			private InputStream stream;
			private byte[] buf = new byte[1024];
			private int curChar;
			private int numChars;
			private SpaceCharFilter filter;
			private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	 
			public InputReader(InputStream stream)
			{
				this.stream = stream;
			}
			
			public int read()
			{
				if (numChars==-1) 
					throw new InputMismatchException();
				
				if (curChar >= numChars)
				{
					curChar = 0;
					try 
					{
						numChars = stream.read(buf);
					}
					catch (IOException e)
					{
						throw new InputMismatchException();
					}
					
					if(numChars <= 0)				
						return -1;
				}
				return buf[curChar++];
			}
		 
			public String nextLine()
			{
				String str = "";
	            try
	            {
	                str = br.readLine();
	            }
	            catch (IOException e)
	            {
	                e.printStackTrace();
	            }
	            return str;
			}
			public int nextInt()
			{
				int c = read();
				
				while(isSpaceChar(c)) 
					c = read();
				
				int sgn = 1;
				
				if (c == '-') 
				{
					sgn = -1;
					c = read();
				}
				
				int res = 0;
				do 
				{
					if(c<'0'||c>'9') 
						throw new InputMismatchException();
					res *= 10;
					res += c - '0';
					c = read();
				}
				while (!isSpaceChar(c)); 
				
				return res * sgn;
			}
			
			public long nextLong() 
			{
				int c = read();
				while (isSpaceChar(c))
					c = read();
				int sgn = 1;
				if (c == '-') 
				{
					sgn = -1;
					c = read();
				}
				long res = 0;
				
				do 
				{
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					res *= 10;
					res += c - '0';
					c = read();
				}
				while (!isSpaceChar(c));
					return res * sgn;
			}
			
			public double nextDouble() 
			{
				int c = read();
				while (isSpaceChar(c))
					c = read();
				int sgn = 1;
				if (c == '-') 
				{
					sgn = -1;
					c = read();
				}
				double res = 0;
				while (!isSpaceChar(c) && c != '.') 
				{
					if (c == 'e' || c == 'E')
						return res * Math.pow(10, nextInt());
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					res *= 10;
					res += c - '0';
					c = read();
				}
				if (c == '.') 
				{
					c = read();
					double m = 1;
					while (!isSpaceChar(c)) 
					{
						if (c == 'e' || c == 'E')
							return res * Math.pow(10, nextInt());
						if (c < '0' || c > '9')
							throw new InputMismatchException();
						m /= 10;
						res += (c - '0') * m;
						c = read();
					}
				}
				return res * sgn;
			}
			
			public String readString() 
			{
				int c = read();
				while (isSpaceChar(c))
					c = read();
				StringBuilder res = new StringBuilder();
				do 
				{
					res.appendCodePoint(c);
					c = read();
				} 
				while (!isSpaceChar(c));
				
				return res.toString();
			}
		 
			public boolean isSpaceChar(int c) 
			{
				if (filter != null)
					return filter.isSpaceChar(c);
				return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
			}
		 
			public String next() 
			{
				return readString();
			}
			
			public interface SpaceCharFilter 
			{
				public boolean isSpaceChar(int ch);
			}
		}
	 	
		public static void main(String[] args) throws Exception
		{
			new Thread(null, new Main(),"Main",1<<26).start();
		}
		
	    public class Pair<E1,E2> {
	    	E1 first;
	    	E2 second;
	    	Pair(E1 first,E2 second) {
	    		this.first = first;
	    		this.second = second;
	    	}
	    	@Override
	    	public String toString() {
				return "("+first+","+second+")";
	    	}
			@Override
			public boolean equals(Object obj) {
				Pair<E1,E2> p = (Pair<E1, E2>) obj;
				if(first.equals(p.first) && second.equals(p.second))return true;
				return false;
			}
	    }
	    
	    static InputReader sc = new InputReader(System.in);
	    static PrintWriter w = new PrintWriter(System.out);;

	    //[a,a] [a+1,a+k] [2a+2,2a+2k] [4a+4,4a+4k] [8a+8,8a+8k] [2^(i-1)a + 2^(i-1), 2^(i-1)a + 2^(i-1)k] 
	    //    1            2              3         4             5
	    //            4,5         8,10             [16,20]       36
	    // 	3		4			9			18
	    // k=2
	    // a=3
	      long pow(long a, int b)
	      {
	            if ( b == 0)        return 1;
	            if ( b == 1)        return a;
	            if ( b % 2 == 0)    return pow ( a * a, b/2); //even a=(a^2)^b/2
	            else                return a * pow ( a * a, b/2); //odd  a=a*(a^2)^b/2
	      }
	    
	    
	    public void run() {
	    	int n = sc.nextInt();

	    	int m = (n/2) + 1;

	    	List< Pair<Integer,Integer > > positions = new ArrayList<>();

	    	for(int i=1,x=1,y=1;i<=n;i++) {
	    		if(y>m) {
	    			x++;
	    			positions.add(new Pair(x,m));	
	    		} else {
	                  positions.add(new Pair(x,y));
	    			y++;
	    		}
	    	}
	    	
	    	w.println(m);
	    	
	    	for(int i=0;i<positions.size();i++)
	    	      for(int j=i+1;j<positions.size();j++)
	    	            if(Math.abs(positions.get(i).first-positions.get(j).first)+
	    	                  Math.abs(positions.get(i).second-positions.get(j).second) < Math.abs(j-i))
	    	                  w.println("oh "+ i + " " + j + " = " + positions.get(i) + " " + positions.get(j));
	    	
	    	for(Pair<Integer,Integer> point : positions) {
	    		w.println(point.first + " " + point.second);
	    	}
	    	
	    	w.close();
	    }
	}