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\times 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|\ge|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\le n\le 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\le r_i,c_i\le 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\times1$ chessboard without breaking the rule. But you can place two pieces on a $2\times2$ chessboard like this:

[Image]

In the second example, you can't place four pieces on a $2\times2$ 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\times3$ chessboard, you can place four pieces like this:

[Image]

Difficulty: interview

Starter code:

Solutions:
n = int(input())
m = (n + 2) // 2
d = [0, 1]
print(m)
for i in range(1, n + 1):
    if d[0] < m:
        d[0] += 1
        print(*d)
    else:
        d[1] += 1
        print(*d)



def main():
    buf = input()
    n = int(buf)
    m = n // 2 + 1
    print(m)
    for i in range(m):
        print(1, i+1)
        n -= 1
    for i in range(m):
        if n > 0:
            print(i+2, m)
            n -= 1

def __starting_point():
    main()

__starting_point()

# coding: utf-8

import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(list(range(len(l))), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: list(map(int, input().split()))
MIL = lambda: list(MI())
MIS = lambda: input().split()


def main():
    N = II()
    M = math.ceil((N + 1) / 2)
    print(M)
    x, y = 1, 1
    for i in range(1, N + 1):
        print(x, y)
        if i % 2 == 0:
            y += 1
        else:
            x += 1


def __starting_point():
    main()

__starting_point()

#	!/usr/bin/env python3
#	encoding: UTF-8
#	Modified: <07/Jun/2019 05:47:40 PM>


#	✪ H4WK3yE乡
#	Mohd. Farhan Tahir
#	Indian Institute Of Information Technology (IIIT), Gwalior


import sys


def get_array(): return list(map(int, sys.stdin.readline().split()))


def get_ints(): return list(map(int, sys.stdin.readline().split()))


def input(): return sys.stdin.readline().strip()


def main():
    n = int(input())
    ans = n // 2 + 1
    print(ans)
    r = 0
    c = 1
    for i in range(1, n + 1):
        if i % 2 == 1:
            r += 1
        else:
            c += 1
        print(r, c)


def __starting_point():
    main()

__starting_point()

n=int(input())
print(n//2+1)
for c in range(1,n+1):
    if c<=(n//2+1):
        print(c,1)
    else:
        print(n//2+1,c-n//2)


n = int(input())
m = (n + 2) // 2
print(m)
for i in range(m):
    print(1, i + 1)
for i in range(n - m):
    print(m, i+2)

n = int(input())
a = []
print(n // 2 + 1)
for i in range(n // 2):
  print(i + 1, i + 1)
  print(i + 1, i + 2)
if n % 2 == 1:
  print((n + 1) // 2, (n + 1) // 2)


n = int(input())
m = (n + 1) // 2 + (n + 1) % 2
if n == 1:
    print(1)
    print(1, 1)
else:
    print(m)
    for i in range(1, m + 1):
        print(1, i)
    for i in range(2, n - m + 2):
        print(i, m)


from math import ceil
n = int(input())
ans = ceil((n+1)/2)
print(ans)
x = y = 1
for i in range(n):
    print(x,y)
    if x != ans: x+=1
    else: y += 1


def __starting_point():
  n = int(input())
  # n - 1 <= 2m - 2, m >= (n + 1) / 2
  m = int(n / 2 + 1)
  print(m)
  for i in range(1, n + 1):
    if i <= m:
      print(1, i)
    else:
      print(i - m + 1, m)

__starting_point()

n = int(input())
print(n//2+1)

r = 1
c = 1
for i in range(n):
    print(r,c)
    if i%2==0:
        c+=1
    else:
        r+=1

n = int(input())
m = n // 2 + 1
print(m)
for i in range(1, n // 2 + 1):
	print(1, i)
M = 1
for i in range(n // 2 + 1, n + 1):
	print(m, M)
	M += 1

import sys
import math
from itertools import permutations
input = sys.stdin.readline

n=int(input())

minn=n//2 + 1
print(minn)
for i in range(minn):
	print(1,i+1)
left=n-minn
for i in range(left):
	print(i+2,minn)

n = int(input())
t = n//2+1
print(t)
for i in range(1,t+1):
    print(i,'1')
if n % 2:
    for i in range(2,t+1):
        print(t,i)
else:
    for i in range(2, t):
        print(t,i)

n = int(input())

m = n // 2 + 1

r = 1
c = 1
print(m)
for i in range(n):
    print(r, c)
    if i % 2 == 0:
        c += 1
    else:
        r += 1

n = int(input())
m = n // 2 + 1

print(m)
i, j = 1, 1
for _ in range(n):
    print(i, j)
    if i == j:
        j += 1
    else:
        i += 1

n=int(input())
a=(n+1)//2+(n+1)%2
print(a)
lx=1
ly=1
for i in range(n):
    if ly<a:
        print(ly,lx)
        ly+=1
    else:
        print(ly,lx)
        lx+=1


n = int(input())
print(n // 2 + 1)
for i in range(n):
    print(1 + (n // 2) * ((i) // (n // 2 + 1)), i % (n // 2 + 1) + 1 + i // (n // 2 + 1))

n = int(input())
if n % 2 == 0:
    print(n // 2 + 1)
else:
    print((n + 1) // 2)
i = j = 1
for _ in range(1, n + 1):
    print(i, j)
    if i == j:
        j += 1
    else:
        i += 1


def main():
    n = int(input())
    m = n // 2 + 1
    print(m)
    for i in range(m):
        print(str(i + 1) + " 1")
    for i in range(m + 1, n + 1):
        print(str(m) + " " + str(i - m + 1))


def __starting_point():
    main()

__starting_point()

n = int(input())
if n == 1:
    print(1)
    print(1,1)
else:
    x = (n) // 2 + 1
    print(x)
    i = 1
    j = 1
    for k in range(n):
        print(i, j)
        i += (k % 2 == 0)
        j += (k % 2)

n = int(input())
if n%2:
	size = (n+1)//2
else:
	size = n//2+1
print(size)
for i in range(n):
	if i < size:
		print(1, i+1)
	else:
		print(i-size+2, size)

from collections import defaultdict as dd
import math
import sys
input=sys.stdin.readline
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))

n=nn()

size=(n+2)//2

print(size)


for i in range(size):
	print(1, i+1)

for j in range(n-size):
	print(j+2,size)








n = int(input())
m = n // 2 + 1
print(m)
a = 1
b = 1
for i in range(n):
	print(a, b)
	if a < m:
		a += 1
	else:
		b += 1

#m >= (n + 1)/2

n = int(input())

m = (n + 1)//2 + (n + 1)%2

left = n
print(m)
for i in range(1, m + 1):
    if(left == 0):
        break
    print(1, i)    
    left -= 1
    
for i in range(2, m+1):
    if(left == 0):
        break
    left -= 1
    
    print(i, m)