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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class ProblemB {
	public static void main(String [] args) throws IOException{
	solve();	}
	
	
	
	
	
public static void solve() throws IOException {
	Scanner sc = new Scanner(System.in);
	int n=sc.nextInt();
	int m=0;
	StringBuilder sb = new StringBuilder("");
	for(int i=1;i<1000;i++) {
		if(n-1<= 2*(i-1)) {
			m=i;
			break;
		}
	}
	int k=1;
	int arr [][] = new int[m][m];
all:	for(int i=0;i<m;i++) {
		for(int j=0;j<m;j++) {
			if(k-1<= ((i+1)-1)+((j+1)-1)) {
				if(k>n) break all;
				arr[i][j]=k;
				sb.append((i+1)+" "+(j+1)+"\n");
				k++;
			}
		}
	}
	System.out.println(m);
	System.out.println(sb);
	
}
	
	
	
	
	
	
	
static void shuffle(long[] a)
{
	int n = a.length;
	for(int i = 0; i < n; i++)
	{
		int r = i + (int)(Math.random() * (n - i));
		long tmp = a[i];
		a[i] = a[r];
		a[r] = tmp;
	}
}
	
	
	
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;
 
		public Scanner(InputStream s){
			br = new BufferedReader(new InputStreamReader(s));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}
		 
				public String nextLine() throws IOException {return br.readLine();}
		 
				public double nextDouble() throws IOException
				{
					String x = next();
					StringBuilder sb = new StringBuilder("0");
					double res = 0, f = 1;
					boolean dec = false, neg = false;
					int start = 0;
					if(x.charAt(0) == '-')
					{
						neg = true;
						start++;
					}
					for(int i = start; i < x.length(); i++)
						if(x.charAt(i) == '.')
						{
							res = Long.parseLong(sb.toString());
							sb = new StringBuilder("0");
							dec = true;
						}
						else
						{
							sb.append(x.charAt(i));
							if(dec)
								f *= 10;
						}
					res += Long.parseLong(sb.toString()) / f;
					return res * (neg?-1:1);
				}
		 
				public boolean ready() throws IOException {return br.ready();}
	}
 
}