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.*;

public class B{
  final int mod = 1000000007;
  final int maxn = -1;
  final double eps = 1e-9;

  void main(){
    // freopen("in");
    int n = nextInt();
    printf("%d\n", n / 2 + 1);
    int i;
    for(i = 1; i <= n / 2 + 1; ++i){
      printf("%d 1\n", i);
    }
    for(int j = 2; i <= n; ++i, ++j){
      printf("%d %d\n", n / 2 + 1, j);
    }
  }

  final double pi = Math.acos(-1.0);
  final long infl = 0x3f3f3f3f3f3f3f3fl;
  final int inf = 0x3f3f3f3f;
  final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;

  boolean zero(double x){ return x < eps; }

  PrintWriter out = new PrintWriter(System.out);
  BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 15);
  StringTokenizer tokens = new StringTokenizer("");

  B(){
    Locale.setDefault(Locale.US);       // imprime double com ponto
    main();
    out.close();
  }

  void freopen(String s){ try{ reader = new BufferedReader(new InputStreamReader(new FileInputStream(s)), 1 << 15); } catch(FileNotFoundException e){ throw new RuntimeException(e); } }

  int nextInt(){ return Integer.parseInt(next()); }
  long nextLong(){ return Long.parseLong(next()); }
  double nextDouble(){ return Double.parseDouble(next()); }
  String next(){ readTokens(); return tokens.nextToken(); }
  String nextLine(){ readTokens(); return tokens.nextToken("\n"); }

  void readTokens(){
    while(!tokens.hasMoreTokens())      // lê os dados, ignorando linhas vazias
      try{ tokens = new StringTokenizer(reader.readLine()); } catch(IOException e){ throw new RuntimeException(e); }
  }

  void printf(String s, Object... o){ out.printf(s, o); }
  void debug(String s, Object... o){ if(!ONLINE_JUDGE) System.err.printf((char)27 + "[91m" + s + (char)27 + "[0m", o); }

  public static void main(String[] args){ new B(); }
}