You are given an integer $n$.

You should find a list of pairs $(x_1, y_1)$, $(x_2, y_2)$, ..., $(x_q, y_q)$ ($1 \leq x_i, y_i \leq n$) satisfying the following condition.

Let's consider some function $f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ (we define $\mathbb{N}$ as the set of positive integers). In other words, $f$ is a function that returns a positive integer for a pair of positive integers.

Let's make an array $a_1, a_2, \ldots, a_n$, where $a_i = i$ initially.

You will perform $q$ operations, in $i$-th of them you will:   assign $t = f(a_{x_i}, a_{y_i})$ ($t$ is a temporary variable, it is used only for the next two assignments);  assign $a_{x_i} = t$;  assign $a_{y_i} = t$. 

In other words, you need to simultaneously change $a_{x_i}$ and $a_{y_i}$ to $f(a_{x_i}, a_{y_i})$. Note that during this process $f(p, q)$ is always the same for a fixed pair of $p$ and $q$.

In the end, there should be at most two different numbers in the array $a$.

It should be true for any function $f$.

Find any possible list of pairs. The number of pairs should not exceed $5 \cdot 10^5$.


-----Input-----

The single line contains a single integer $n$ ($1 \leq n \leq 15\,000$).


-----Output-----

In the first line print $q$ ($0 \leq q \leq 5 \cdot 10^5$) — the number of pairs.

In each of the next $q$ lines print two integers. In the $i$-th line print $x_i$, $y_i$ ($1 \leq x_i, y_i \leq n$).

The condition described in the statement should be satisfied.

If there exists multiple answers you can print any of them.


-----Examples-----
Input
3

Output
1
1 2

Input
4

Output
2
1 2
3 4



-----Note-----

In the first example, after performing the only operation the array $a$ will be $[f(a_1, a_2), f(a_1, a_2), a_3]$. It will always have at most two different numbers.

In the second example, after performing two operations the array $a$ will be $[f(a_1, a_2), f(a_1, a_2), f(a_3, a_4), f(a_3, a_4)]$. It will always have at most two different numbers.

Difficulty: MEDIUM

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10 ** 3)

def f(lo, hi):
	n = hi - lo
	if n == 2:
		return [(lo, lo + 1)]
	l = f(lo, lo + n // 2) + f(lo + n // 2, hi)
	for i in range(n // 2):
		l.append((lo + i, hi - i - 1))
	return l
N = int(input())
if N == 1:
	print(0)
	raise SystemExit
k = 1
while 2 ** (k + 1) <= N:
	k += 1
l = f(0, 2 ** k)
if 2 ** k != N:
	l.extend(f(N - 2 ** k, N))
print(len(l))
R = []
for (a, b) in l:
	R.append(f'{a + 1} {b + 1}')
print('\n'.join(R))


def pairss(n):
	res = []
	i = 1
	while i < n:
		for k in range(0, n, i * 2):
			for j in range(i):
				res.append((j + k, j + i + k))
		i *= 2
	return res
n = int(input())
z = 1
while z * 2 < n:
	z *= 2
q = pairss(z)
res = []
for (a, b) in q:
	res.append((a + 1, b + 1))
for (a, b) in q:
	res.append((n - a, n - b))
print(len(res))
for (a, b) in res:
	print(a, b)


n = int(input())

def f(x, a):
	if x == 2:
		return [(a, a + 1)]
	else:
		s = []
		for i in range(x // 2):
			s += [(a + i, a + i + x // 2)]
		return f(x // 2, a) + f(x // 2, x // 2 + a) + s
if n == 0 or n == 1:
	print(0)
else:
	x = 1
	for i in range(1, n):
		if 2 * x > n:
			break
		x *= 2
	s1 = f(x, 1)
	s2 = f(x, n - x + 1)
	print(len(s1) + len(s2))
	for i in range(len(s1)):
		print(s1[i][0], s1[i][1])
	for i in range(len(s2)):
		print(s2[i][0], s2[i][1])


n = int(input())
if n <= 2:
	print(0)
	exit()
m = 1
while 2 * m < n:
	m *= 2
ans = []
for i in range(m.bit_length()):
	d = 2 ** i
	s = set()
	for j in range(m):
		if j in s:
			continue
		if j + d >= m:
			break
		ans.append([j, j + d])
		s.add(j + d)
for i in range(m.bit_length()):
	d = 2 ** i
	s = set()
	for j in range(n - m, n + 1):
		if j in s:
			continue
		if j + d >= n:
			break
		ans.append([j, j + d])
		s.add(j + d)
print(len(ans))
for (a, b) in ans:
	print(a + 1, b + 1)


import sys
input = sys.stdin.readline
import math

def solve(n, i):
	global ans
	if n == 2:
		ans.append([i, i + 1])
	else:
		solve(n // 2, i)
		solve(n // 2, i + n // 2)
		for j in range(n // 2):
			ans.append([i + j, i + j + n // 2])
n = int(input())
if n == 1:
	print(0)
	quit()
ans = []
k = math.floor(math.log2(n))
solve(2 ** k, 0)
solve(2 ** k, n - 2 ** k)
for i in range(n - 2 ** k):
	ans.append([i, i + 2 ** k])
print(len(ans))
for pair in ans:
	print(pair[0] + 1, pair[1] + 1)


import io
import os
from collections import Counter, defaultdict, deque

def solve(N):

	def gen(N):
		pairs = []
		for p in range(1, 15):
			stride = 2 ** p
			extras = []
			for i in range(1, N + 1, stride):
				if i + stride - 1 <= N:
					for j in range(i, i + stride // 2):
						extras.append((j, j + stride // 2))
			pairs += extras
		return pairs
	pow2 = 1
	while pow2 * 2 <= N:
		pow2 *= 2
	pairs = gen(N) + [(N - i + 1, N - j + 1) for (i, j) in gen(pow2)]
	return str(len(pairs)) + '\n' + '\n'.join((str(x) + ' ' + str(y) for (x, y) in pairs))
if False:
	for N in range(3, 100):
		pairs = solve(N).split('\n')[1:]
		assert len(pairs) <= 5 * 10 ** 5
		A = list(range(1, N + 1))
		f = defaultdict(lambda : len(f))
		print(N, pairs)
		for ij in pairs:
			(i, j) = [int(x) - 1 for x in ij.split()]
			t = f[A[i], A[j]]
			A[i] = t
			A[j] = t
			print(ij, A)
		print(N, pairs)
		print(A)
		assert len(set(A)) <= 2
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = [int(x) for x in input().split()]
ans = solve(N)
print(ans)


import sys

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def string(s):
	return ''.join(s)

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def bo(i):
	return ord(i) - ord('A')

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

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

def gh():
	sys.stdout.flush()

def isvalid(i, j):
	return 0 <= i < n and 0 <= j < m and (a[i][j] != '.')

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = 1
ans = []

def rec(s, size):
	if size < 2:
		return
	if size == 2:
		ans.append([s, s + 1])
		return
	rec(s, size // 2)
	rec(s + size // 2, size // 2)
	for i in range(size // 2):
		ans.append([s + i, s + i + size // 2])
while t > 0:
	t -= 1
	n = fi()
	p = len(bin(n)[2:]) - 1
	rec(1, 2 ** p)
	if n != 2 ** p:
		rec(n - 2 ** p + 1, 2 ** p)
	print(len(ans))
	for i in ans:
		print(*i)


n = int(input())
if n == 1:
	print(0)
	exit()
N = (n - 1).bit_length() - 1
M = 2 ** N
print(M // 2 * N * 2)
for i in range(N):
	x = 2 ** i
	for j in range(1, M, x * 2):
		for k in range(x):
			print(j + k, j + k + x)
for i in range(N):
	x = 2 ** i
	for j in range(n, n - M + 1, -x * 2):
		for k in range(x):
			print(j - k, j - x - k)


n = int(input())
out = []

def p(a, b, d):
	out.append(str(a + 1 + d) + ' ' + str(b + 1 + d))
p2 = 1
while 2 * p2 <= n:
	p2 *= 2
for d in (0, n - p2):
	bit = 1
	while bit < p2:
		for i in range(p2):
			if i ^ bit > i:
				p(i, i ^ bit, d)
		bit *= 2
print(len(out))
print('\n'.join(out))


import sys
input = sys.stdin.readline
n = int(input())
A = []
start = 0
while True:
	for i in range(30):
		if start + (1 << i) > n:
			A.append(list(range(start + 1, 1 + start + (1 << i - 1))))
			start = start + (1 << i - 1)
			break
	if start == n:
		break
ANS = []

def combine(x, y):
	m = y - x + 1
	step = 1
	while m >= 1:
		step += 1
		m //= 2
	for k in range(step):
		USE = [0] * (n + 1)
		for i in range(x, y + 1):
			if i + (1 << k) > y:
				break
			if USE[i] == 0:
				ANS.append((i, i + (1 << k)))
				USE[i] = 1
				USE[i + (1 << k)] = 1
for xlist in A:
	if len(xlist) == 1:
		continue
	else:
		(x, y) = (xlist[0], xlist[-1])
		combine(x, y)
while len(A) > 2:
	if len(A[-1]) == len(A[-2]):
		for i in range(len(A[-1])):
			ANS.append((A[-2][i], A[-1][i]))
		x = A.pop()
		A[-1] += x
	else:
		X = []
		for i in range(len(A[-1])):
			x = A[0].pop()
			A[0].append(x - 1)
			ANS.append((x, A[-1][i]))
			X.append(x)
		A[-1] += X
print(len(ANS))
for (x, y) in ANS:
	print(x, y)


import sys

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

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def pairss(n):
	res = []
	i = 1
	while i < n:
		for k in range(0, n, i * 2):
			for j in range(i):
				res.append((j + k, j + i + k))
		i *= 2
	return res
n = mint()
z = 1
while z * 2 < n:
	z *= 2
q = pairss(z)
res = []
for (a, b) in q:
	res.append((a + 1, b + 1))
for (a, b) in q:
	res.append((n - a, n - b))
print(len(res))
for (a, b) in res:
	print(a, b)


import math
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(100000)

def put():
	return map(int, stdin.readline().split())
for _ in range(1):
	n = int(input())
	group = 2
	main = []
	import math
	a = 2 ** int(math.log(n, 2))
	while group <= 2 ** int(math.log(n, 2)):
		for i in range(0, a, group):
			for j in range(group // 2):
				if i + j + 1 + group // 2 <= n:
					main.append([i + j + 1, i + j + 1 + group // 2])
		group *= 2
	offset = n - 2 ** int(math.log(n, 2))
	group = 2
	while group < n:
		for i in range(offset, n, group):
			for j in range(group // 2):
				if i + j + 1 + group // 2 <= n:
					main.append([i + j + 1, i + j + 1 + group // 2])
		group *= 2
	print(len(main))
	for i in range(len(main)):
		print(main[i][0], main[i][1])


import math
n = int(input())
e = math.floor(math.log2(n))
m = pow(2, e)
j = 1
k = e
res = []
nq = 0
while k > 0:
	for i in range(m // 2):
		jpow = pow(2, j)
		jpowmin = pow(2, j - 1)
		p = min(jpow * (i // jpowmin) + 1 + 0 + i % jpowmin, n)
		q = min(jpow * (i // jpowmin) + 1 + jpowmin + i % jpowmin, n)
		res.append(str(p) + ' ' + str(q))
		nq += 1
	j += 1
	k -= 1
if m != n:
	j = 1
	k = e
	d = n - m
	while k > 0:
		for i in range(m // 2):
			jpow = pow(2, j)
			jpowmin = pow(2, j - 1)
			p = jpow * (i // jpowmin) + 1 + 0 + i % jpowmin + d
			q = jpow * (i // jpowmin) + 1 + jpowmin + i % jpowmin + d
			res.append(str(p) + ' ' + str(q))
			nq += 1
		j += 1
		k -= 1
print(nq)
for i in range(len(res)):
	print(res[i])


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	if n != 1:
		m = 1
		cnt = 0
		while 2 * m < n:
			m *= 2
			cnt += 1
		print(cnt * m)
		ansCnt = cnt * m
		for i in range(cnt):
			gap = 2 ** i
			for j in range(m):
				if j ^ gap > j:
					print(str(j + 1) + ' ' + str((j ^ gap) + 1))
					ansCnt -= 1
		for i in range(cnt):
			gap = 2 ** i
			for j in range(m):
				if j ^ gap > j:
					print(str(j + 1 + n - m) + ' ' + str((j ^ gap) + 1 + n - m))
					ansCnt -= 1
	else:
		print(0)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def foo(p):
	if p == 0:
		return []
	l = foo(p - 1)
	res = []
	for t in l:
		res += [t]
	n = 2 ** (p - 1)
	for t in l:
		(x, y) = t
		res += [(x + n, y + n)]
	for i in range(n):
		res += [(i, i + n)]
	return res

def solve(n):
	p = 0
	while 2 ** p <= n:
		p += 1
	p -= 1
	res = []
	if 2 ** p == n:
		res = foo(p)
	else:
		res = foo(p)
		d = n - 2 ** p
		t = [(x[0] + d, x[1] + d) for x in res]
		res += t
	return list(map(lambda x: (x[0] + 1, x[1] + 1), res))
n = int(input())
res = solve(n)
print(len(res))
for p in res:
	print(p[0], p[1])


def f(r, s, b=0):
	o = []
	d = 1 + b
	while d < s:
		for i in range(0, s // d, 2):
			for j in range(d):
				o.append((r + i * d + j, r + i * d + j + d))
		d *= 2
	return o
n = int(input())
if n < 3:
	print(0)
	quit()
o = []
d = 1
while d < n:
	d *= 2
d //= 2
e = 1
while e <= n - d:
	e *= 2
o += f(1, d)
g = {}
for i in range(e + d - n):
	o.append((d - i, i + d + 1))
	g[n - e + 1 + 2 * i] = d - i
	g[n - e + 2 + 2 * i] = i + d + 1
for i in range(2 * d - n + e + 1, n, 2):
	o.append((i, i + 1))
	g[i] = i
	g[i + 1] = i + 1
for i in f(n - e + 1, e, 1):
	o.append((g[i[0]], g[i[1]]))
print(len(o))
print('\n'.join(map(lambda x: str(x[0]) + ' ' + str(x[1]), o)))


import sys
input = sys.stdin.readline
ans = []

def solve(n, start):
	if n == 1:
		return
	solve(n // 2, start)
	solve(n // 2, start + n // 2)
	for i in range(n // 2):
		ans.append([start + i, start + i + n // 2])

def main():
	n = int(input())
	s = format(n, 'b')
	bin_s = [1]
	for i in range(len(s) - 1):
		bin_s.append(bin_s[-1] * 2)
	bin_s = bin_s[::-1]
	total = 1
	lst = [[] for _ in range(len(s))]
	for (j, (ss, bb)) in enumerate(zip(s, bin_s)):
		if ss == '1':
			for i in range(total, total + bb):
				lst[j].append(i)
			solve(bb, total)
			total += bb
	lst2 = lst[1:].copy()
	lst2 = lst2[::-1]
	zero_pos = 0
	lst0 = lst[0].copy()
	lst3 = []
	for lst in lst2:
		if lst3 == []:
			if lst == []:
				continue
			lst3 = lst.copy()
			tmp_lst = []
			for i in lst3:
				ans.append((i, lst0[zero_pos]))
				tmp_lst.append(lst0[zero_pos])
				zero_pos += 1
			for num in tmp_lst:
				lst3.append(num)
		elif lst == []:
			tmp_lst = []
			for i in lst3:
				ans.append((i, lst0[zero_pos]))
				tmp_lst.append(lst0[zero_pos])
				zero_pos += 1
			for num in tmp_lst:
				lst3.append(num)
		else:
			for (i, j) in zip(lst3, lst):
				ans.append((i, j))
			for j in lst:
				lst3.append(j)
	print(len(ans))
	for row in ans:
		print(*row)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def pre(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

def prod(a):
	ans = 1
	for each in a:
		ans = ans * each
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

class F:
	ans = []

def solve(x):
	y1 = []
	y2 = []
	for j in range(0, len(x) - 1, 2):
		F.ans += [[x[j], x[j + 1]]]
		y1 += [x[j]]
		y2 += [x[j + 1]]
	if len(x) == 1:
		return
	else:
		solve(y1)
		solve(y2)
for _ in range(int(input()) if not True else 1):
	n = int(input())
	if n <= 2:
		print(0)
		continue
	x = 1
	while 2 * x <= n:
		x *= 2
	solve([i + 1 for i in range(x)])
	solve([n - i for i in range(x)][::-1])
	print(len(F.ans))
	for i in F.ans:
		print(*i)


import sys
readline = sys.stdin.readline
N = int(readline())
if N == 1:
	print(0)
else:
	BN = 1
	while BN * 2 <= N:
		BN *= 2
	Ans = []
	for i in range(BN.bit_length()):
		d = 1 << i
		for j in range(1, BN + 1, 2 * d):
			if j + d > BN:
				break
			for k in range(d):
				Ans.append((j + k, j + k + d))
	Ans = Ans + [(N + 1 - a, N + 1 - b) for (a, b) in Ans]
	print(len(Ans))
	print('\n'.join(('{} {}'.format(*a) for a in Ans)))


n = int(input())
for i in range(20):
	if 2 ** i > n:
		pointer = i
		break
a = 2 ** (pointer - 1)
ans = []
for i in range(pointer - 1):
	pointer2 = 0
	k = 2 ** i
	for j in range(a):
		if j % (2 * k) < k:
			ans.append([str(j + 1), str(j + 1 + k)])
for i in range(pointer - 1):
	pointer2 = 0
	k = 2 ** i
	for j in range(a):
		if j % (2 * k) < k:
			ans.append([str(n - j), str(n - j - k)])
print(len(ans))
for i in ans:
	print(' '.join(i))


import sys, math, cmath, time, collections
start_time = time.time()

def solve():
	n = inp()
	q = []
	w = [0, n - int(pow(2, int(math.log(n, 2))))]
	for i in range(len(w)):
		qw = 1
		while qw < n - w[-1]:
			for j in range(n - w[-1]):
				if j ^ qw >= j:
					q.append([j + w[i] + 1, (j ^ qw) + w[i] + 1])
			qw = qw * 2
	print(len(q))
	print(*[' '.join(map(str, q[i])) for i in range(len(q))], sep='\n')

def main():
	global tt
	if not ONLINE_JUDGE:
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	t = 1
	for tt in range(1, t + 1):
		solve()
	if not ONLINE_JUDGE:
		print('Time Elapsed :', time.time() - start_time, 'seconds')
		sys.stdout.close()

def inp():
	return int(input())

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

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def counter(a):
	q = [0] * max(a)
	for i in range(len(a)):
		q[a[i] - 1] = q[a[i] - 1] + 1
	return q

def counter_elements(a):
	q = dict()
	for i in range(len(a)):
		if a[i] not in q:
			q[a[i]] = 0
		q[a[i]] = q[a[i]] + 1
	return q

def string_counter(a):
	q = [0] * 26
	for i in range(len(a)):
		q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
	return q

def factorial(n, m=1000000007):
	q = 1
	for i in range(n):
		q = q * (i + 1) % m
	return q

def factors(n):
	q = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			q.append(i)
			q.append(n // i)
	return list(sorted(list(set(q))))

def prime_factors(n):
	q = []
	while n % 2 == 0:
		q.append(2)
		n = n // 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			q.append(i)
			n = n // i
	if n > 2:
		q.append(n)
	return list(sorted(q))

def transpose(a):
	(n, m) = (len(a), len(a[0]))
	b = [[0] * n for i in range(m)]
	for i in range(m):
		for j in range(n):
			b[i][j] = a[j][i]
	return b

def ceil(a, b):
	return -(-a // b)
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

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

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = float('inf')
mod = int(1000000000.0) + 7
n = int(data())
a = 1 << len(bin(n)) - 3
i = 1
ans = []
while i < a:
	for j in range(0, a, 2 * i):
		for k in range(i):
			ans.append(str(k + j + 1) + ' ' + str(k + j + i + 1))
	i *= 2
t = n - a
i = 1
while i < a:
	for j in range(0, a, 2 * i):
		for k in range(i):
			ans.append(str(t + k + j + 1) + ' ' + str(t + i + j + k + 1))
	i *= 2
print(len(ans))
print('\n'.join(ans))


def get(res, sp, bn):
	m = 2
	while m <= bn:
		for p in range(0, bn, m):
			for u in range(0, m // 2):
				res.append((sp + p + u + 1, sp + m // 2 + p + u + 1))
		m *= 2
n = int(input())
bn = 2 ** (len(bin(n)) - 3)
res = []
get(res, 0, bn)
if n > bn:
	get(res, n - bn, bn)
print(len(res))
print('\n'.join(['{0} {1}'.format(u, v) for (u, v) in res]))


def calc():
	s = 0
	f = 0
	k = (N - 1).bit_length() - 1
	for _ in range(2):
		for kk in range(k):
			for i in range(0, 1 << k - kk, 2):
				for j in range(1 << kk):
					a = i * (1 << kk) + j + s
					b = a + (1 << kk)
					ANS.append((a, b))
		s += 1 << k
N = int(input())
ANS = []
if N > 1:
	calc()
print(len(ANS))
for (a, b) in ANS:
	print(a % N + 1, b % N + 1)


def f(i, b):
	n = 2 ** b
	for j in range(b):
		for k in range(0, n, 2 ** (j + 1)):
			for l in range(k, k + 2 ** j):
				print(i + l, i + l + 2 ** j)
(N,) = map(int, input().split())
for i in range(1000):
	if 2 ** i > N:
		i -= 1
		break
R = []
if N == 1:
	print(0)
else:
	print(i * 2 ** i)
	f(1, i)
	f(N - 2 ** i + 1, i)


from sys import stdin
import sys

def f(l, r):
	if r == l + 1:
		return [l]
	else:
		LL = f(l, (l + r) // 2)
		RR = f((l + r) // 2, r)
		for i in range(len(LL)):
			ans.append((LL[i], RR[i]))
		return LL + RR
n = int(stdin.readline())
ans = []
t = 1
while t * 2 <= n:
	t *= 2
f(1, t + 1)
f(n + 1 - t, n + 1)
print(len(ans))
for i in ans:
	print(*i)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 10 ** 9 + 7

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def solve(case):
	n = int(inp())
	if n == 1:
		print(0)
		return
	k = 0
	while 2 ** (k + 1) <= n:
		k += 1
	ans = []
	for i in range(1, k + 1):
		for j in range(1, 2 ** k + 1, 2 ** i):
			for kk in range(j, j + 2 ** (i - 1)):
				ans.append((kk, kk + 2 ** (i - 1)))
	temp = n - 2 ** k
	for i in range(1, k + 1):
		for j in range(1, 2 ** k + 1, 2 ** i):
			for kk in range(j, j + 2 ** (i - 1)):
				ans.append((temp + kk, temp + kk + 2 ** (i - 1)))
	print(len(ans))
	for i in range(len(ans)):
		print(ans[i][0], ans[i][1])
testcase(1)


def solve(l, r):
	if r - l > 1:
		mid = (l + r) // 2
		solve(l, mid)
		solve(mid + 1, r)
		for i in range(l, mid + 1):
			ans.append((i, mid + i - l + 1))
	elif r - l == 1:
		ans.append((l, r))
n = int(input())
kiki = 1
while kiki * 2 <= n:
	kiki *= 2
ans = []
solve(1, kiki)
solve(n - kiki + 1, n)
print(len(ans))
for i in ans:
	print(*i)


import sys
import math
input = sys.stdin.readline
n = int(input())
if n == 1:
	print(0)
else:
	ans = []
	xxx = bin(n)
	xxx = xxx[2:]
	xxx = 2 ** (len(xxx) - 1)
	step = 1
	swap = -1
	k = 1
	while True:
		for i in range(0, xxx):
			if i % k == 0:
				swap += 1
			if swap % 2 == 0:
				a = i
				b = a + k
				ans.append((a, b))
		k *= 2
		step *= 2
		if k == xxx:
			break
	tt = len(ans) * 2
	print(tt)
	for (x, y) in ans:
		print(x + 1, y + 1)
	for (x, y) in ans:
		print(n - x, n - y)


n = int(input())
if n != 1:
	m = 1
	cnt = 0
	while 2 * m < n:
		m *= 2
		cnt += 1
	print(cnt * m)
	ansCnt = cnt * m
	for i in range(cnt):
		gap = 2 ** i
		for j in range(m):
			if j ^ gap > j:
				print(str(j + 1) + ' ' + str((j ^ gap) + 1))
				ansCnt -= 1
	for i in range(cnt):
		gap = 2 ** i
		for j in range(m):
			if j ^ gap > j:
				print(str(j + 1 + n - m) + ' ' + str((j ^ gap) + 1 + n - m))
				ansCnt -= 1
else:
	print(0)


def f(x):
	if x == 2:
		return [(1, 2)]
	z = f(x // 2)
	l = list(z)
	for i in z:
		l.append((i[0] + x // 2, i[1] + x // 2))
	for i in range(x // 2):
		l.append((i + 1, i + x // 2 + 1))
	return l
n = int(input())
if n == 1:
	print(0)
	quit()
z = 1
while z <= n:
	z = z * 2
z = z // 2
a = f(z)
print(2 * len(a))
for i in a:
	print(i[0], i[1])
for i in a:
	print(i[0] + n - z, i[1] + n - z)
print()