Every person likes prime numbers. Alice is a person, thus she also shares the love for them. Bob wanted to give her an affectionate gift but couldn't think of anything inventive. Hence, he will be giving her a graph. How original, Bob! Alice will surely be thrilled!

When building the graph, he needs four conditions to be satisfied:   It must be a simple undirected graph, i.e. without multiple (parallel) edges and self-loops.  The number of vertices must be exactly $n$ — a number he selected. This number is not necessarily prime.  The total number of edges must be prime.  The degree (i.e. the number of edges connected to the vertex) of each vertex must be prime. 

Below is an example for $n = 4$. The first graph (left one) is invalid as the degree of vertex $2$ (and $4$) equals to $1$, which is not prime. The second graph (middle one) is invalid as the total number of edges is $4$, which is not a prime number. The third graph (right one) is a valid answer for $n = 4$.  [Image] 

Note that the graph can be disconnected.

Please help Bob to find any such graph!


-----Input-----

The input consists of a single integer $n$ ($3 \leq n \leq 1\,000$) — the number of vertices.


-----Output-----

If there is no graph satisfying the conditions, print a single line containing the integer $-1$.

Otherwise, first print a line containing a prime number $m$ ($2 \leq m \leq \frac{n(n-1)}{2}$) — the number of edges in the graph. Then, print $m$ lines, the $i$-th of which containing two integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$) — meaning that there is an edge between vertices $u_i$ and $v_i$. The degree of each vertex must be prime. There must be no multiple (parallel) edges or self-loops.

If there are multiple solutions, you may print any of them.

Note that the graph can be disconnected.


-----Examples-----
Input
4

Output
5
1 2
1 3
2 3
2 4
3 4
Input
8

Output
13
1 2
1 3
2 3
1 4
2 4
1 5
2 5
1 6
2 6
1 7
1 8
5 8
7 8



-----Note-----

The first example was described in the statement.

In the second example, the degrees of vertices are $[7, 5, 2, 2, 3, 2, 2, 3]$. Each of these numbers is prime. Additionally, the number of edges, $13$, is also a prime number, hence both conditions are satisfied. [Image]

Difficulty: MEDIUM
Tags: Greedy algorithms

Number theory

Mathematics

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
data = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097]
key = int(input())
if key in data:
	print(key)
	for each in range(key):
		print(each % key + 1, (each + 1) % key + 1)
else:
	ans = 0
	for each in data:
		if each > key:
			ans = each
			break
	print(ans)
	x = (ans - key) * 2
	y = key - x
	index_start = 1
	index_mid = 2
	index_end = key
	flag = []
	for each in range(key):
		flag.append(0)
	for each_1 in range(key):
		if each_1 < x:
			sub = flag[index_start - 1]
			for each_2 in range(3 - sub):
				if index_start >= index_mid:
					index_mid = index_start + 1
				print(index_start, index_mid)
				flag[index_start - 1] = flag[index_start - 1] + 1
				flag[index_mid - 1] = flag[index_mid - 1] + 1
				index_mid = index_mid + 1
				if index_mid > index_end:
					index_mid = index_start + 1
			index_start = index_start + 1
		else:
			sub = flag[index_start - 1]
			for each_2 in range(2 - sub):
				if index_start >= index_mid:
					index_mid = index_start + 1
				print(index_start, index_mid)
				flag[index_start - 1] = flag[index_start - 1] + 1
				flag[index_mid - 1] = flag[index_mid - 1] + 1
				index_mid = index_mid + 1
				if index_mid > index_end:
					index_mid = index_start + 1
			index_start = index_start + 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
import math
q = 1
for _ in range(q):
	n = int(input())
	ans = []
	for i in range(n - 1):
		ans.append([i + 1, i + 2])
	ans.append([n, 1])
	if isPrime(n):
		print(len(ans))
		for i in range(len(ans)):
			print(*ans[i])
	else:
		for i in range(n + 1, 3 * n // 2 + 1):
			if isPrime(i):
				ans.append([i - n, i + n // 2 - n])
				break
			else:
				ans.append([i - n, i + n // 2 - n])
		print(len(ans))
		for i in range(len(ans)):
			print(*ans[i])


def primes(n):
	if n <= 2:
		return []
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * int((n - i * i - 1) / (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]
P = primes(2001)
n = int(input())
i = 0
while P[i] < n:
	i += 1
m = P[i]
toprint = []
for i in range(1, n + 1):
	toprint.append([i, i % n + 1])
vis = [False for i in range(n + 1)]
for i in range(1, n + 1):
	if vis[i]:
		continue
	if vis[(i + 1) % n + 1]:
		continue
	vis[i] = True
	vis[(i + 1) % n + 1] = True
	toprint.append([i, (i + 1) % n + 1])
print(m)
if len(toprint) < m:
	print('shit', m, n)
for i in range(m):
	print(*toprint[i])


from bisect import bisect_left as bl

def find_primes(s, n):
	for i in range(51, n, 2):
		flag = 0
		for j in s:
			if j * j > i:
				break
			if i % j == 0:
				flag = 1
				break
		if not flag:
			s.append(i)
s = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
find_primes(s, 1050)
n = int(input())
ans = []
for i in range(1, n):
	ans.append((i, i + 1))
ans.append((n, 1))
edges = n
ind = bl(s, edges)
k = s[ind] - edges
i = 1
for _ in range(k):
	ans.append((i, i + n // 2))
	i += 1
print(len(ans))
for i in ans:
	print(i[0], i[1])


import sys
import math

def isPrime(p):
	for x in range(2, int(math.sqrt(p)) + 1):
		if p % x == 0:
			return False
	return True

def nextPrime(n):
	while not isPrime(n):
		n += 1
	return n
for line in sys.stdin:
	n = int(line)
	if n == 8:
		print(13)
		print('1 2')
		print('1 3')
		print('2 3')
		print('1 4')
		print('2 4')
		print('1 5')
		print('2 5')
		print('1 6')
		print('2 6')
		print('1 7')
		print('1 8')
		print('5 8')
		print('7 8')
		break
	p = nextPrime(n)
	print(p)
	for i in range(1, n + 1):
		print('%d %d' % (i, i % n + 1))
	for i in range(1, p - n + 1):
		print('%d %d' % (3 * i - 2, 3 * i))
	break


p = [True for i in range(1010)]
p[0] = False
p[1] = False
i = 2
while i < 1010:
	curr = i
	while curr * i < 1010:
		p[curr * i] = False
		curr += 1
	i += 1
n = int(input())
ans = []
c = 0
for i in range(1, n + 1):
	if i == n:
		ans.append([i, 1])
		c += 1
	else:
		ans.append([i, i + 1])
		c += 1
for i in range(1, n // 2 + 1):
	if p[c] == True:
		break
	ans.append([i, i + n // 2])
	c += 1
print(len(ans))
for i in ans:
	print(i[0], i[1])


from bisect import bisect_left as bl
N = 1010
X = [-1] * N
k = 2
while k < N:
	X[k] = 1
	for i in range(k * 2, N, k):
		X[i] = 0
	while k < N and X[k] >= 0:
		k += 1
P = [i for i in range(N) if X[i] == 1]
ANS = []

def a1(i):
	ANS.append((i, i + 1))
	ANS.append((i, i + 2))
	ANS.append((i, i + 3))
	ANS.append((i + 1, i + 2))
	ANS.append((i + 2, i + 3))

def a2(i):
	ANS.append((i, i + 1))
	ANS.append((i, i + 2))
	ANS.append((i, i + 3))
	ANS.append((i + 1, i + 2))
	ANS.append((i + 1, i + 3))
	ANS.append((i + 2, i + 3))

def a0(i):
	for j in range(i - 1):
		ANS.append((j + 1, j + 2))
	ANS.append((1, i))

def calc(x, y):
	if x == 0:
		return 0
	if x < 3:
		print('NG')
		return 0
	if y == 0:
		a0(x)
		return 0
	if y > 1:
		a2(x - 3)
		calc(x - 4, y - 2)
		return 0
	a1(x - 3)
	calc(x - 4, y - 1)
n = int(input())
if n == 6:
	print(7)
	print(1, 2)
	print(1, 3)
	print(2, 3)
	print(3, 4)
	print(4, 5)
	print(4, 6)
	print(5, 6)
else:
	a = P[bl(P, n)]
	calc(n, a - n)
	print(len(ANS))
	for ans in ANS:
		print(*ans)


import sys
import bisect
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]
n = int(input())
edge = []
degree = [0] * 1020
for i in range(2, n + 1):
	edge.append([i - 1, i])
	degree[i - 1] += 1
	degree[i] += 1
edge.append([n, 1])
degree[n] += 1
degree[1] += 1
ind = bisect.bisect_left(prime, n)
diff = prime[ind] - n
(i, j) = (1, 1)
while diff >= i:
	if degree[j] == 2:
		edge.append([j, j + 2])
		degree[j] += 1
		degree[j + 2] += 1
		i += 1
	j += 1
print(prime[ind])
for i in edge:
	sys.stdout.write(' '.join(map(str, i)) + '\n')


primes = [2]

def tryp(num):
	bound = num ** 0.5
	for p in primes:
		if p > bound:
			primes.append(num)
			return
		if num % p == 0:
			return
for num in range(3, 1100, 2):
	tryp(num)
n = int(input())
if n == 2:
	print(-1)
	import sys
	sys.exit()
p = -1
for pr in primes:
	if pr >= n:
		p = pr
		break
print(p)
dif = p - n
print(1, n)
for i in range(1, n):
	print(i, i + 1)
for i in range(1, dif + 1):
	print(i, i + n // 2)


prime = []
maxn = 100000
G = []

def init():
	for i in range(1007):
		G.append([])
		for j in range(1007):
			G[i].append(0)

def sieve():
	for i in range(maxn):
		prime.append(1)
	prime[0] = prime[1] = 0
	for i in range(maxn):
		if prime[i]:
			j = 2 * i
			while j < maxn:
				prime[j] = 0
				j += i
init()
sieve()
n = eval(input())
tot = 0
for i in range(1, n):
	G[i][i + 1] = 1
	tot += 1
G[1][n] = 1
tot += 1
j = n - 1
i = 1
while j > i:
	if prime[tot]:
		break
	G[i][j] = 1
	tot += 1
	i += 1
	j -= 1
print(tot)
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if G[i][j]:
			print(str(i) + ' ' + str(j))


def is_prime(a):
	i = 2
	while i * i <= a:
		if a % i == 0:
			return False
		i += 1
	return True
n = int(input())
ans = n
while not is_prime(ans):
	ans += 1
ans = ans - n
l = [[1, n]]
for i in range(n - 1):
	l.append([i + 1, i + 2])
for i in range(1, ans + 1):
	l.append([i, i + n // 2])
print(len(l))
for i in range(len(l)):
	print(l[i][0], l[i][1])


def isPrime(n):
	return all((n % x != 0 for x in range(2, int(n ** 0.5 + 2))))
n = int(input())
m = n
edges = []
for i in range(n - 1):
	edges.append([i + 1, i + 2])
edges.append([n, 1])
index = 1
while not isPrime(m):
	m += 1
	right = index + n // 2
	if right > n:
		right -= n
	edges.append([index, right])
	index += 1
print(m)
for edge in edges:
	print(' '.join(map(str, edge)))


import sys
import math
from collections import defaultdict, deque
input = sys.stdin.readline

def inar():
	return [int(el) for el in input().split()]

def prime(num):
	if num == 1:
		return False
	for i in range(2, int(num ** 0.5) + 1):
		if num % i == 0:
			return False
	return True

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


from math import sqrt

def is_prime(n):
	if n % 2 == 0 and n > 2:
		return False
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			return False
	return True
n = int(input())
k = n
while not is_prime(k):
	k += 1
print(k)
print(1, n)
for i in range(n - 1):
	print(i + 1, i + 2)
for i in range(k - n):
	print(i + 1, i + 1 + n // 2)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	pp = []
	for p in range(2, n + 1):
		if prime[p]:
			pp.append(p)
	return pp

def f(n):
	Primes = SieveOfEratosthenes(10000)
	deg = 0
	for i in Primes:
		if i >= n:
			deg = i
			break
	a = []
	cnt = [0] * n
	cnt[0] += 1
	cnt[n - 1] += 1
	a.append((1, n))
	for i in range(n - 1):
		a.append((i + 1, i + 2))
		cnt[i] += 1
		cnt[i + 1] += 1
	req = deg - len(a)
	l = 0
	r = n - 2
	c = 2
	for i in range(req):
		a.append((l + 1, r + 1))
		cnt[l] += 1
		cnt[r] += 1
		if r == l + 1:
			l = 0
			c += 1
			r = n - c
		else:
			l += 1
			r -= 1
	print(len(a))
	for i in a:
		print(*i)
	return ''
print(f(int(input())))


n = int(input())

def is_prime(n):
	i = 2
	otv = 10
	while i * i <= n:
		if n % i == 0:
			otv = 'composite'
			i = n
		else:
			i += 1
	if otv == 'composite':
		return otv
	else:
		otv = 'prime'
		return otv
plus = n
for i in range(n, n + n // 2):
	ans = is_prime(i)
	if ans == 'prime':
		plus = i
		break
plus = plus - n
arr = []
for i in range(n):
	arr.append([i + 1, i + 2])
arr[-1][1] = 1
for i in range(1, plus + 1):
	arr.append([i, i + n // 2])
print(n + plus)
for j in range(n + plus):
	for i in range(2):
		print(arr[j][i], end=' ')
	print()


a = []

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			a.append(p)
nn = 2030
n = int(input())
SieveOfEratosthenes(nn)
ans = []
p = n - 1
if n in a:
	print(n)
	print(n, 1)
	for i in range(1, n):
		print(i, i + 1)
	exit()
for i in range(1, len(a) - 1):
	if a[i] == p:
		p = a[i - 1]
		break
	elif a[i + 1] > p and a[i] < p:
		p = a[i - 1]
		break
for i in range(2, p + 2):
	ans.append([1, i])
l = n - 1 + p
for i in range(len(a) - 1):
	if a[i] == l:
		ll = a[i]
		break
	elif a[i + 1] > l and a[i] < l:
		ll = a[i]
		break
cnt = 0
r = l - ll
for i in range(2, n):
	if i % 2 == 1 and cnt < r:
		cnt += 1
		continue
	ans.append([i, i + 1])
ans.append([2, n])
print(len(ans))
for i in range(len(ans)):
	print(*ans[i])


import os, sys
mod = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip('\r\n')
from bisect import bisect_left
from math import sqrt, ceil, gcd
from _collections import deque
ar = [1] * 10001
for i in range(2, 101):
	if ar[i] == 1:
		for j in range(i * i, 10001, i):
			ar[j] = 0
pr = []
for i in range(2, 1010):
	if ar[i]:
		pr.append(i)
n = int(input())
t = bisect_left(pr, n)
print(pr[t])
for i in range(1, n):
	print(i, i + 1)
print(n, 1)
for i in range(pr[t] - n):
	print(i + 1, n // 2 + i + 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 nextprime(n):
	for i in range(n, 2 * n + 1):
		if isPrime(i):
			return i

def arun(i, n):
	while i < n:
		print(i, i + 1)
		i += 1
	print(1, n)
n = int(input())
next = nextprime(n)
print(next)
arun(1, n)
tot = n
(i, j) = (1, n - 1)
while i < j and tot != next:
	tot += 1
	print(i, j)
	i += 1
	j -= 1


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')

def prime(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
n = int(input())
m = n
while prime(n) == False:
	n += 1
print(n)
print(1, m)
print(1, 2)
for i in range(1, m - 1):
	print(i + 1, i + 2)
t = 1
for i in range(n - m):
	print(t, t + n // 2)
	t += 1


def er(x):
	p = [True] * (x + 1)
	p[0] = p[1] = False
	ans = []
	for i in range(2, x + 1):
		if p[i]:
			ans.append(i)
			for j in range(i * i, x + 1, i):
				p[j] = False
	return ans
n = int(input())
p = er(n * (n - 1) // 2)
for i in p:
	if i >= n:
		k = i
		break
print(k)
for i in range(1, n):
	print(i, i + 1)
print(1, n)
v = [1] * n
i = 1
while k > n:
	if v[i] == 1:
		print(i, i + 2)
		v[i] += 1
		v[i + 2] += 1
		i += 1
		k -= 1
	else:
		i += 1


def checkPrime(n):
	for i in range(2, 1 + int(n ** 0.5)):
		if n % i == 0:
			return False
	return True
n = int(input())
edges = n
while not checkPrime(edges):
	edges += 1
ans = []
for i in range(n):
	ans.append((i + 1, 1 + (i + 1) % n))
edges -= n
i = 1
for i in range((n - 2) // 2):
	if edges > 0:
		ans.append((i + 1, n - i - 1))
		edges -= 1
if edges:
	print(-1)
else:
	print(len(ans))
	for i in ans:
		print(*i)


import math

def is_prime(x):
	if x == 1:
		return False
	if x == 2:
		return True
	for i in range(3, int(math.sqrt(x + 1)) + 1, 2):
		if x % i == 0:
			return False
	return True
n = int(input())

def main(n):
	if n % 2 == 1:
		e = 0
	else:
		e = 1
	while not is_prime(n + e):
		e += 2
	edges = [(i, i + 1) for i in range(1, n)] + [(n, 1)]
	i = 1
	while e >= 10:
		edges.extend([(i, i + 2), (i, i + 3), (i, i + 4), (i, i + 5), (i, i + 6)])
		edges.extend([(i + 1, i + 7), (i + 1, i + 8), (i + 1, i + 9), (i + 1, i + 10), (i + 1, i + 11)])
		i = i + 12
		e -= 10
	if e >= 5:
		edges.extend([(i, i + 2), (i, i + 3), (i, i + 4), (i, i + 5), (i, i + 6)])
		i += 7
		e -= 5
	if e == 4:
		edges.extend([(i, i + 2), (i, i + 3), (i, i + 4), (i + 1, i + 5)])
	elif e == 3:
		edges.extend([(i, i + 2), (i, i + 3), (i, i + 4)])
	elif e == 2:
		edges.extend([(i, i + 2), (i + 1, i + 3)])
	elif e == 1:
		edges.extend([(i, i + 2)])
	assert len(edges)
	edgecount = [0] * (n + 1)
	for edge in edges:
		edgecount[edge[0]] += 1
		edgecount[edge[1]] += 1
	for c in edgecount:
		assert is_prime(c)
	print(len(edges))
	for edge in edges:
		print(edge[0], edge[1])
main(n)


import sys
import math
p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499]
n = int(input())
arr = []
for i in range(n - 1):
	arr.append([i + 1, i + 2])
arr.append([1, n])
x = 0
while p[x] < n:
	x += 1
d = p[x] - n
for i in range(d):
	arr.append([i + 1, n - i - 1])
print(len(arr))
for i in range(len(arr)):
	print(*arr[i])


line = input()
tmp = int(line)

def is_prime(x):
	for i in range(2, x):
		if x % i == 0:
			return False
	return True

def find_next_prime(x):
	x = x + 3
	while not is_prime(x):
		x = x + 1
	return x

def find_last_prime(x):
	while not is_prime(x):
		x = x - 1
	return x
if tmp == 4:
	print(5)
	print('1 2')
	print('1 3')
	print('2 3')
	print('2 4')
	print('3 4')
elif tmp == 6:
	print(7)
	print('1 2')
	print('1 3')
	print('2 3')
	print('4 5')
	print('5 6')
	print('4 6')
	print('1 4')
elif is_prime(tmp):
	print(tmp)
	print(1, tmp)
	for i in range(1, tmp):
		print(i, i + 1)
else:
	np = find_next_prime(tmp)
	m = np - tmp
	print(np)
	print(1, m)
	for i in range(1, m):
		print(i, i + 1)
	c = m + 1
	print(c, tmp)
	for i in range(c, tmp):
		print(i, i + 1)
	for i in range(m):
		print(1 + i, 1 + i + m)


from math import *

class Graph:

	def __init__(self, n):
		self.noOfEdges = 0
		self.degree = [0 for i in range(n)]
		self.arr = [[] for i in range(n)]
		for i in range(n - 1):
			self.addEdge(i, i + 1)
		self.addEdge(n - 1, 0)

	def addEdge(self, i, j):
		self.arr[i].append(j)
		self.arr[j].append(i)
		self.noOfEdges += 1
		self.degree[i] += 1
		self.degree[j] += 1

def binarySearch(primes, x, n):
	l = 0
	r = n - 1
	while l <= r:
		mid = (l + r) // 2
		if primes[mid] >= x:
			r = mid - 1
		else:
			l = mid + 1
	return l
primes = [2, 3]
for i in range(5, 1010, 2):
	x = floor(sqrt(i)) + 2
	j = 3
	flag = 0
	while j < x:
		if i % j == 0:
			flag = 1
			break
		j += 2
	if flag == 0:
		primes.append(i)
n = int(input())
g = Graph(n)
l1 = binarySearch(primes, n, len(primes))
x = primes[l1] - g.noOfEdges
if x > n // 2:
	x = n // 2
for i in range(x):
	if i % 2 == 0:
		g.addEdge(2 * i, 2 * i + 2)
	else:
		g.addEdge(2 * i + 1, 2 * i + 3)
graph = [[0 for i in range(n)] for i in range(n)]
if g.noOfEdges == primes[l1]:
	print(g.noOfEdges)
	for i in range(n):
		x = g.arr[i]
		for j in x:
			if graph[i][j] == 1:
				continue
			else:
				graph[i][j] = 1
				graph[j][i] = 1
				print(i + 1, j + 1)


ll = lambda : list(map(int, input().split()))
testcases = 1
prime = []

def seive(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
for testcase in range(testcases):
	prime = seive(2005)
	[n] = ll()
	ii = n
	while prime[ii] != True:
		ii += 1
	ans = []
	for i in range(1, n):
		ans.append([i, i + 1])
	ans.append([n, 1])
	ii -= n
	if ii == 0:
		print(len(ans))
		for i in ans:
			print(*i)
		continue
	done = 1
	while ii != 0:
		ans.append([done, (done + 2) % (n + 1)])
		done += (done & 1 == 0) * 2
		done += 1
		ii -= 1
	print(len(ans))
	for i in ans:
		print(*i)


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
ans = []
n = int(input())
for i in range(n - 1):
	ans.append([i + 1, i + 2])
ans.append([n, 1])
x = n
if not isPrime(n):
	for i in range(n // 2 + 1):
		ans.append([i + 1, n // 2 + i + 1])
		x += 1
		if isPrime(x):
			break
print(len(ans))
for i in range(len(ans)):
	print(*ans[i])


primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999]
n = int(input())
edge = 2 + 3 * (n // 3)
if n == 7:
	print(7)
	print('1 2\n1 4\n2 3\n3 4\n5 6\n5 7\n6 7')
else:
	if n % 3 == 1:
		outString = '1 2\n1 3\n1 4\n2 3\n2 4\n'
		first = 5
	elif n % 3 == 2:
		outString = '1 2\n1 5\n2 3\n3 4\n4 5\n'
		first = 6
	else:
		outString = '1 2\n1 3\n2 3\n'
		edge -= 2
		first = 4
	for i in range((n - 3) // 3):
		outString = outString + str(first + i * 3) + ' ' + str(first + i * 3 + 1) + '\n' + str(first + i * 3) + ' ' + str(first + i * 3 + 2) + '\n' + str(first + i * 3 + 1) + ' ' + str(first + i * 3 + 2) + '\n'
	val = 0
	while primes[val] < edge:
		val += 1
	leastPrime = primes[val]
	print(leastPrime)
	current = 3
	for i in range(leastPrime - edge):
		outString = outString + str(current) + ' ' + str(current + 3) + '\n'
		if (current - 5) % 3 == 0 and current != 3:
			current += 4
		else:
			current += 1
	print(outString)


3
import math
import sys
DEBUG = False

def inp():
	return sys.stdin.readline().rstrip()

def dprint(*value, sep=' ', end='\n'):
	if DEBUG:
		print(*value, sep=sep, end=end)

def is_prime(a):
	x = 2
	while x * x <= a:
		if a % x == 0:
			return False
		x += 1
	return True

def main():
	N = int(inp())
	p = N
	while not is_prime(p):
		p += 1
	diff = p - N
	assert diff <= N // 2
	print(p)
	for i in range(N):
		print(i + 1, (i + 1) % N + 1)
	i = 1
	j = 1 + N // 2
	while diff > 0:
		print(i, j)
		i += 1
		j += 1
		diff -= 1

def __starting_point():
	main()
__starting_point()


import bisect
import decimal
from decimal import Decimal
import os
from collections import Counter
import bisect
from collections import defaultdict
import math
import random
import heapq
from math import sqrt
import sys
from functools import reduce, cmp_to_key
from collections import deque
import threading
from itertools import combinations
from io import BytesIO, IOBase
from itertools import accumulate
from random import randint
decimal.getcontext().prec = 46

def primeFactors(n):
	prime = set()
	while n % 2 == 0:
		prime.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			prime.add(i)
			n = n // i
	if n > 2:
		prime.add(n)
	return list(prime)

def getFactors(n):
	factors = []
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				factors.append(i)
			else:
				factors.append(i)
				factors.append(n // i)
		i = i + 1
	return factors

def modefiedSieve():
	mx = 10 ** 7 + 1
	sieve = [-1] * mx
	for i in range(2, mx):
		if sieve[i] == -1:
			sieve[i] = i
			for j in range(i * i, mx, i):
				if sieve[j] == -1:
					sieve[j] = i
	return sieve

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	num = []
	for p in range(2, n + 1):
		if prime[p]:
			num.append(p)
	return num

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

def sort_dict(key_value):
	return sorted(key_value.items(), key=lambda kv: (kv[1], kv[0]))

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

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

def string_list():
	return list(input())

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def binaryToDecimal(n):
	return int(n, 2)

def DFS(n, s, adj):
	visited = [False for i in range(n + 1)]
	stack = []
	stack.append(s)
	while len(stack):
		s = stack[-1]
		stack.pop()
		if not visited[s]:
			visited[s] = True
		for node in adj[s]:
			if not visited[node]:
				stack.append(node)

def maxSubArraySum(a, size):
	maxint = 10 ** 10
	max_so_far = -maxint - 1
	max_ending_here = 0
	for i in range(0, size):
		max_ending_here = max_ending_here + a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
	return max_so_far

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():
	n = int(input())
	N = n
	if isPrime(n):
		print(n)
		for i in range(n - 1):
			print(i + 1, i + 2)
		print(n, 1)
	else:
		for i in range(n + 1, 2000):
			if isPrime(i):
				n = i
				break
		print(n)
		for i in range(N - 1):
			print(i + 1, i + 2)
		print(N, 1)
		(u, v) = (1, N - 1)
		for i in range(n - N):
			print(u, v)
			u += 1
			v -= 1
t = 1
for _ in range(t):
	solve()


def kiemtra(a):
	if a > 1:
		a2 = int(a // 2)
		for i in range(2, a2 + 1):
			if int(a % i) == 0:
				return 0
		return 1
	else:
		return 0
n = int(input())
e = []
for i in range(n - 1):
	e.append([i + 1, i + 2])
e.append([1, n])
l = len(e)
kt = kiemtra(l)
bac = [2] * n
bd = 1
while kt != 1:
	e.append([bd, bd + int(n // 2)])
	bd += 1
	l += 1
	kt = kiemtra(l)
l = len(e)
print(l)
for i in range(l):
	print(e[i][0], e[i][1])


from sys import stdin, stdout, exit
huge_p = 998244353
N = 10 ** 6
ps = [True] * N
for i in range(2, N):
	if ps[i]:
		for k in range(2 * i, N, i):
			ps[k] = False

def opp(i):
	return (i + n // 2) % n
n = int(input())
for i in range(n // 2):
	if ps[n + i]:
		stdout.write(str(n + i) + '\n')
		for j in range(n):
			stdout.write(str(j + 1) + ' ' + str((j + 1) % n + 1) + '\n')
		for j in range(i):
			stdout.write(str(j + 1) + ' ' + str(opp(j) + 1) + '\n')
		exit()
print(-1)


def make_prime_table(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n ** 0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(2 * i, n + 1, i):
			is_prime[j] = False
	return is_prime
li = make_prime_table(10000)
n = int(input())
ans = []
for i in range(n - 1):
	ans.append((i + 1, i + 2))
ans.append((i + 2, 1))
s = 0
t = n - 2
while not li[len(ans)]:
	ans.append((s + 1, t + 1))
	s += 1
	t -= 1
print(len(ans))
for i in range(len(ans)):
	print(' '.join(map(str, ans[i])))


from math import sqrt, ceil

def prime(n):
	if n <= 1:
		return False
	elif not 1 & n and (not n ^ 2):
		return False
	for i in range(2, ceil(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
n = int(input())
for i in range(n, 3 * n // 2 + 2):
	if prime(i):
		break
print(i)
for p in range(1, n):
	print(p, p + 1)
print(n, 1)
for p in range(i - n):
	print(p + 1, p + 1 + n // 2)


import math

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
	r = math.sqrt(n)
	while i <= r:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def nextPrime(n):
	for i in range(n, 3 * n // 2 + 1):
		if isPrime(i):
			return i
n = int(input())
n2 = nextPrime(n)
print(n2)
for i in range(1, n):
	print(i, end=' ')
	print(i + 1)
print(n, 1)
n1 = n2 - n
i = 1
while n1:
	print(i, i + n // 2)
	n1 -= 1
	i += 1


import math
twopower = 0
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]

def primeFactors(n):
	global twopower
	ans = []
	while n % 2 == 0:
		twopower += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			ans.append(i)
			n = n / i
	if n > 2:
		ans.append(int(n))
	return (ans, twopower)

def create_list(start, p):
	for i in range(start, start + p - 1):
		edgelist.append((i, i + 1))
	edgelist.append((i + 1, start))
	end = i + 1
	return end

def create_four_list(start):
	for i in range(start, start + 3):
		edgelist.append((i, i + 1))
	edgelist.append((i - 1, i + 1))
	edgelist.append((start, start + 2))
	end = start + 3
	return end

def closest_prime(n):
	import bisect
	p = primes[bisect.bisect_left(primes, n)]
	return p
from collections import Counter
n = int(input())
(pfactors, twopower) = primeFactors(n)
edgelist = []
closest_p = closest_prime(n)
diff = closest_p - n
create_list(1, n)
if diff == 0:
	print(closest_p)
	for edge in edgelist:
		print(*edge)
else:
	start = 1
	flag = 0
	s = set()
	while diff != 0:
		if start not in s:
			edgelist.append((start, start + 2))
			s.add(start)
			s.add(start + 2)
			diff -= 1
		start += 1
		if start == n - 1:
			flag = 1
			break
	if flag and diff != 0:
		print(-1)
	else:
		print(closest_p)
		for edge in edgelist:
			print(*edge)


def isPrime(n):
	d = 2
	bound = n ** 0.5
	while n % d and d <= bound:
		d += 1
	return d * d > n
k = int(input())
for nx in range(k, 10 ** 10):
	if isPrime(nx):
		break
d = nx - k
g = [[1, k]]
st = ['a'] + [2] * k
for i in range(1, k):
	g.append([i, i + 1])
j = 1
for l in range(d):
	for i in range(1, k + 1):
		if st[i] == 2:
			break
	for j in range(i + 2, k + 1):
		if st[j] == 2:
			break
	g.append([i, j])
	st[i] = 3
	st[j] = 3
else:
	print(len(g))
	for i in g:
		print(*i)


n = int(input())
check = n - n % 2 + 1
while True:
	done = True
	for guy in range(2, int(check ** 0.5 + 1)):
		if check % guy == 0:
			check += 2
			done = False
			break
	if done:
		break
extra = check - n
print(check)
for i in range(n - 1):
	print(i + 1, i + 2)
print(n, 1)
for i in range(extra):
	print(i + 1, i + n // 2 + 1)


def prime(n, primes):
	return primes[n]

def seive(n):
	primes = [True] * n
	for i in range(2, n):
		if primes[i]:
			j = 2
			while i * j < n:
				primes[i * j] = False
				j += 1
	primes[0] = False
	primes[1] = False
	return primes

def main():
	primes = seive(10 ** 6 + 1)
	n = int(input())
	edges = []
	for i in range(n):
		if i == n - 1:
			edges.append((n, 1))
		else:
			edges.append((i + 1, i + 2))
	if not prime(len(edges), primes):
		found = False
		start = 1
		end = n - 1
		for i in range(n // 2 - 1):
			edges.append((start, end))
			if prime(len(edges), primes):
				found = True
				break
			start += 1
			end -= 1
		if not found:
			edges.append((start, n))
			if prime(len(edges), primes):
				found = True
		if not found:
			print(-1)
			return
	print(len(edges))
	for i in edges:
		print(i[0], i[1])
main()


def nextPrime(arr, num):
	(start, end) = (0, len(arr) - 1)
	while start <= end:
		mid = start + (end - start) // 2
		if arr[mid] == num:
			return num
		if arr[mid] > num:
			end = mid - 1
		else:
			start = mid + 1
	return arr[start]
n = int(input())
isPrime = [True] * n ** 2
primes = []
isPrime[0] = isPrime[1] = False
for i in range(2, len(isPrime)):
	if isPrime[i]:
		primes.append(i)
		curr = 2 * i
		while curr < len(isPrime):
			isPrime[curr] = False
			curr += i
edges = []
maxDiff = 0
for i in range(len(primes) - 1):
	maxDiff = max(maxDiff, primes[i + 1] - primes[i])
count = n
for i in range(1, n + 1):
	if i != n:
		edges.append((i, i + 1))
	else:
		edges.append((n, 1))
e = nextPrime(primes, count)
done = set()
diff = e - count
i = 1
while diff != 0:
	if i not in done and i + 2 not in done:
		edges.append((i, i + 2))
		done.add(i)
		done.add(i + 2)
		diff -= 1
	i += 1
print(e)
for edge in edges:
	print(*edge)


from math import ceil, floor, sqrt, log

def mod_expo(n, p, m):
	result = 1
	while p != 0:
		if p % 2 == 1:
			result = result * n % m
		p //= 2
		n = n * n % m
	return result

def is_prime(n):
	for i in range(2, floor(sqrt(n) + 1)):
		if n % i == 0:
			return False
	return True

def find_k(n):
	for k in range(0, ceil(n / 2) + 1):
		if is_prime(k + n):
			return k

def get_graph(n):
	k = find_k(n)
	m = n + k
	print(m)
	for i in range(1, n):
		print(i, i + 1)
	print(n, 1)
	for i in range(1, k + 1):
		print(i, i + floor(n / 2))
t = 1
while t:
	t = t - 1
	n = int(input())
	get_graph(n)


prime = [1 for i in range(2001)]

def SieveOfEratosthenes(n):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = 0
		p += 1
n = int(input())
if n < 3:
	print(-1)
else:
	SieveOfEratosthenes(2000)
	la = n
	for i in range(n, 2001):
		if prime[i] == 1:
			la = i
			break
	print(la)
	for i in range(n - 1):
		print(i + 1, i + 2)
	print(n, 1)
	for i in range(la - n):
		print(i + 1, i + 1 + n // 2)


import bisect
n = int(input())

def primelist(N):
	prime = [2]
	for i in range(3, N + 1):
		flag = 1
		for j in prime:
			if i % j == 0:
				flag = 0
				break
		if flag == 1:
			prime.append(i)
	return prime
prime = primelist(n + 100)
ans = []
for i in range(n - 1):
	ans.append([i + 1, i + 2])
ans.append([1, n])
index = bisect.bisect_left(prime, n)
more = prime[index] - n
mid = n // 2
for i in range(1, more + 1):
	ans.append([i, mid + i])
print(len(ans))
for i in range(len(ans)):
	print(' '.join(map(str, ans[i])))


n = int(input())
i = n
x = 0
while True:
	for j in range(2, i):
		if i % j == 0:
			i += 1
			break
	else:
		x = i - n
		break
array = []
for i in range(1, n):
	array.append((i, i + 1))
array.append((1, n))
i = 1
m = set()
while x != 0:
	if i in m:
		i += 1
		continue
	array.append((i, i + 2))
	m.add(i)
	m.add(i + 2)
	x -= 1
	i += 1
print(len(array))
for el in array:
	print(*el)


prime = [-1] * 2001
for i in range(2, 2001):
	if prime[i] == -1:
		for j in range(i, 2001, i):
			prime[j] = i
n = int(input())
e = []
for i in range(n):
	e.append((i, (i + 1) % n))
if prime[n] == n:
	print(len(e))
	for i in e:
		print(i[0] + 1, i[1] + 1)
else:
	i = 1
	j = n - 1
	while prime[n] != n:
		e.append((i, j))
		i += 1
		j -= 1
		n += 1
	print(len(e))
	for i in e:
		print(i[0] + 1, i[1] + 1)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

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

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	z = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]
	primes = {}
	for i in z:
		primes[i] = 1
	for _ in range(1):
		n = ri()
		ne = {}
		ans = []
		for i in range(1, n + 1):
			k = i + 1
			if i + 1 > n:
				k = 1
			ans.append([i, k])
			ne[i] = 2
		total = n
		i = 1
		while not total in primes and i + 2 <= n:
			j = (i + 2) % n
			if ne[i] == 2 and ne[j] == 2:
				ans.append([i, j])
				total += 1
				ne[i] += 1
				ne[j] += 1
			i += 1
		print(total)
		for i in ans:
			print(*i)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			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, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			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()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

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

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


n = int(input())
l = [(i, i + 1) for i in range(1, n)]
l.append((n, 1))
cnt = n

def is_prime(k):
	j = 2
	while j * j <= k:
		if k % j == 0:
			return False
		j += 1
	return True
for i in range(1, n - 1):
	if is_prime(cnt):
		break
	cnt += 1
	l.append((i, n - i))
print(cnt)
for i in l:
	print(i[0], i[1])


from collections import *
N = 500000
(prim, graph) = (defaultdict(lambda : 1, {i: 1 for i in range(N + 1)}), defaultdict(list))

def count_prime(n):
	prim[0] = prim[1] = 0
	i = 2
	while i * i <= n:
		if prim[i]:
			for j in range(i * 2, n + 1, i):
				prim[j] = 0
		i += 1
	return list(filter(lambda x: prim[x], prim.keys()))

def form_graph(ext):
	for i in range(1, n):
		graph[i].append(i + 1)
	graph[n].append(1)
	num = 1
	for i in range(ext):
		graph[num].append(num + n // 2)
		num += 1
	print(n + ext)
	for i in graph.keys():
		for j in graph[i]:
			print(i, j)
(n, primes, ext) = (int(input()), count_prime(N), 0)
for i in range(N):
	if prim[n + i]:
		ext = i
		break
form_graph(ext)


n = int(input())

def is_prime(x):
	d = 2
	while d * d <= x:
		if x % d == 0:
			return 0
		d += 1
	return 1
i = n
while not is_prime(i):
	i += 1
print(i)
for j in range(n - 1):
	print(j + 1, j + 2)
print(n, 1)
for j in range(i - n):
	print(j + 1, j + n // 2 + 1)


a = []
b = [1] * 1010
for i in range(2, 33):
	if b[i]:
		j = 2
		while i * j < 1010:
			b[i * j] = 0
			j += 1
for i in range(2, 1010):
	if b[i]:
		a.append(i)
n = int(input())
p = n
(l, h) = (0, 168)
if not n in a:
	while l <= h:
		m = (l + h) // 2
		if a[m] > n:
			p = a[m]
			h = m - 1
		else:
			l = m + 1
print(p)
for i in range(1, n):
	print(i, i + 1)
print(1, n)
j = n // 2 + 1
i = 1
p -= n
while p:
	print(i, j)
	i += 1
	j += 1
	p -= 1


import sys
import math
from collections import defaultdict, deque
import heapq
n = int(sys.stdin.readline())
m = 5000
primes = [True for _ in range(m + 1)]
primes[0] = False
primes[1] = False
p = 2
while p * p <= m:
	if primes[p]:
		i = p * p
		while i <= m:
			primes[i] = False
			i += p
	p += 1
edges = -1
for k in range(n, m + 1):
	if primes[k]:
		edges = k
		break
print(edges)
cnt = 0
graph = defaultdict(list)
cur = 1
for i in range(1, n + 1):
	if i + 1 <= n:
		graph[i].append(i + 1)
	else:
		graph[i].append(1)
	cnt += 1
(l, r) = (1, n // 2 + 1)
lim = n // 2 + 1
while l < lim and cnt < edges:
	graph[l].append(r)
	l += 1
	r += 1
	cnt += 1
for i in graph:
	for j in graph[i]:
		print(i, j)


n = int(input())

def prime(x):
	for i in range(2, x):
		if x % i == 0:
			return False
	return True
p = n
while not prime(p):
	p += 1
print(p)
for i in range(1, n):
	print(i, i + 1)
print(1, n)
for i in range(1, p - n + 1):
	print(i, n - i)


def isPrime(x):
	for i in range(2, int(x ** 0.5 + 1)):
		if x % i == 0:
			return False
	return True
n = int(input())
edges = []
for i in range(n - 1):
	edges.append(str(i + 1) + ' ' + str(i + 2))
edges.append(str(n) + ' ' + str(1))
start = 1
while not isPrime(len(edges)):
	edges.append(str(start) + ' ' + str(n - start))
	start += 1
print(len(edges))
print('\n'.join(edges))


from __future__ import print_function
from collections import Counter, OrderedDict
from itertools import permutations as perm
from fractions import Fraction
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()
if n < 3:
	print(-1)
	exit()
cnt = n
N = int(2000.0)
p = [1] * (N + 1)
p[0] = p[1] = 0
N_ = ceil(sqrt(N)) + 1
for i in range(N_):
	if p[i] and i <= N_:
		for j in range(i + i, N + 1, i):
			p[j] = 0
ans = []
i = 1
while p[cnt] == 0:
	ans.append(str(i) + ' ' + str(i + n // 2))
	i += 1
	cnt += 1
for i in range(1, n + 1):
	ans.append(str(i) + ' ' + str(i + 1 if i + 1 <= n else 1))
print(cnt)
print('\n'.join(ans))


import math
n = int(input())

def isPrime(x):
	if x in [2, 3, 5, 7]:
		return True
	if x == 1:
		return False
	for i in range(2, int(math.sqrt(x)) + 1):
		if x % i == 0:
			return False
	return True
ans = []
for i in range(1, n):
	ans.append([i, i + 1])
ans.append([n, 1])
k = 1
if isPrime(n) == False:
	while True:
		ans.append([k, k + n // 2])
		if isPrime(n + k):
			break
		k += 1
print(len(ans))
for x in ans:
	print(*x)


def isp(n):
	for i in range(2, n):
		if n % i == 0:
			return False
	return True
n = int(input())
e = [[i + 1, (i + 1) % n + 1] for i in range(n)]
i = 0
while not isp(len(e)):
	e.append([i + 1, (i + n // 2) % n + 1])
	i += 1
print(len(e))
for ed in e:
	print(*sorted(ed))


def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
n = int(input())
edges = [(i, i % n + 1) for i in range(1, n + 1)]
n_edg = n
i = 1
while not is_prime(n_edg):
	edges.append((i, n // 2 + i))
	n_edg += 1
	i += 1
print(n_edg)
for e in edges:
	print(*e)


import sys
input = sys.stdin.readline

def isPrime(n):
	if n == 2 or n == 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	w = 2
	sqN = int(pow(n, 0.5))
	while i <= sqN:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True
n = int(input())
edges = []
for i in range(1, n):
	edges.append((i, i + 1))
edges.append((n, 1))
ind = 1
while not isPrime(n):
	edges.append((ind, ind + 2))
	n += 1
	if isPrime(n):
		break
	edges.append((ind + 1, ind + 3))
	n += 1
	if isPrime(n):
		break
	ind += 4
print(len(edges))
for edge in edges:
	print(*edge)


def is_prime(n):
	if n == 2 or n == 3:
		return True
	if n < 2 or n % 2 == 0:
		return False
	if n < 9:
		return True
	if n % 3 == 0:
		return False
	r = int(n ** 0.5)
	f = 5
	while f <= r:
		if n % f == 0:
			return False
		if n % (f + 2) == 0:
			return False
		f += 6
	return True
n = int(input())
c = 0
lines = []
for i in range(n):
	lines.append(str(i + 1) + ' ' + str((i + 1) % n + 1))
	c += 1
h = n // 2
for i in range(h):
	if is_prime(c):
		break
	lines.append(str(i + 1) + ' ' + str(i + h + 1))
	c += 1
print(len(lines))
for line in lines:
	print(line)


flags = [True for i in range(3000)]
flags[0] = False
flags[1] = False
for i in range(3000):
	if flags[i]:
		for j in range(i * i, 3000, i):
			flags[j] = False
n = int(input())
a = []
b = []
for i in range(n):
	a.append(i)
	b.append((i + 1) % n)
pos = 0
sz = n
while not flags[sz]:
	a.append(pos)
	b.append(pos + n // 2)
	pos += 1
	sz += 1
print(sz)
for i in range(sz):
	print(str(a[i] + 1) + ' ' + str(b[i] + 1))


def isPrime(n):
	if n <= 1:
		return 0
	for i in range(2, n):
		if n % i == 0:
			return 0
	return 1
n = int(input())
e = n
while True:
	if isPrime(e):
		break
	else:
		e += 1
if n <= 2:
	print(-1)
else:
	print(e)
	for i in range(n - 1):
		print(i + 1, i + 2)
		e -= 1
	j = 0
	while e > 0:
		if j + 1 + 1 == n - j:
			break
		print(j + 1, n - j)
		j += 1
		e -= 1
	if e == 1:
		print(1, n // 2 + 1)


from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353

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

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if not n % i:
			return 0
	return 1
n = val()
if n < 3:
	print(-1)
	exit()
d = defaultdict(set)
tot = 1
d[1].add(n)
d[n].add(1)
for i in range(1, n):
	tot += 1
	d[i].add(i + 1)
	d[i + 1].add(i)
i = 1
while i < n + 1:
	for j in range(1, n + 1):
		if j != i and j not in d[i]:
			d[i].add(j)
			d[j].add(i)
			tot += 1
			i += 1
			break
	dontbreak = 0
	for k in range(n + 1):
		if not isprime(len(d[k])):
			dontbreak = 1
			i = k
			if len(d[k]) == n - 1:
				print(-1)
				exit()
			break
	if dontbreak:
		continue
	if isprime(tot):
		break
if not isprime(tot):
	print(-1)
	exit()
print(tot)
for i in d:
	for j in d[i]:
		if i > j:
			print(i, j)


prime = 998244353
n = int(input())
if n == 2:
	print(1)
else:
	N = 1020
	prime = [True for i in range(N + 1)]
	cur = 2
	while cur ** 2 <= N:
		if prime[cur]:
			for i in range(cur ** 2, N + 1, cur):
				prime[i] = False
		cur += 1
	ans = n
	while not prime[ans]:
		ans += 1
	count = 1
	edges = [(1, n)]
	for i in range(1, n):
		edges.append((i, i + 1))
		count += 1
	flip = 0
	cur = 1
	while count != ans:
		if flip == 0:
			edges.append((cur, cur + 2))
			count += 1
			flip = 1
		else:
			edges.append((cur + 1, cur + 3))
			count += 1
			flip = 0
			cur = cur + 4
	print(ans)
	for (i, j) in edges:
		print(i, j)


from sys import stdin, stdout
import collections
N = int(input())

def is_prime(a):
	return all((a % i for i in range(2, a)))
res = N
while not is_prime(res):
	res += 1
print(res)
for i in range(N - 1):
	print(i + 1, i + 2)
print(N, 1)
half = N // 2 + 1 * (N % 2 == 1)
for i in range(res - N):
	print(i + 1, i + 1 + half)


import sys
import os
from io import BytesIO, IOBase

def ceil(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

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

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

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

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return defaultdict(int)

def ddl():
	return defaultdict(list)

def ddd():
	return defaultdict(defaultdict(int))
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 collections import defaultdict

def isPrime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
for _ in range(1):
	n = ii()
	m = n
	while not isPrime(m):
		m += 1
	print(m)
	for i in range(n - 1):
		print(i + 1, i + 2)
	print(n, 1)
	for i in range(m - n):
		print(i + 1, i + 1 + n // 2)


N = 1200
p = [1] * N
p[0] = p[1] = 0
for i in range(2, N):
	if p[i] == 0:
		continue
	for j in range(i * i, N, i):
		p[j] = 0
primes = [i for i in range(2, N) if p[i]]
n = int(input())
cnt = n
while not p[cnt]:
	cnt += 1
ans = [(i + 1, (i + 1) % n + 1) for i in range(n)]
k = 1
while len(ans) < cnt:
	ans.append((k, k + 2))
	k += 3
res = str(len(ans)) + '\n'
for i in ans:
	res += ' '.join(map(str, i)) + '\n'
if n == 8:
	res = '13\n1 2\n1 3\n2 3\n1 4\n2 4\n1 5\n2 5\n1 6\n2 6\n1 7\n1 8\n5 8\n7 8'
print(res)


n = int(input())

def primes(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n ** 0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
prime2000 = primes(2000)
edge = [(n, 1)]
for i in range(1, n):
	edge.append((i, i + 1))
edge_num = len(edge)
base = 1
while edge_num not in prime2000:
	edge.append((base, n - base))
	base += 1
	edge_num += 1
print(edge_num)
for (a, b) in edge:
	print(str(a) + ' ' + str(b))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
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')

def prime(n):
	c = 0
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			c += 1
			if i % i != n:
				c += 1
	if c == 0:
		return True
	else:
		return False
n = int(input())
m = list()
for i in range(1, n + 1):
	if i != n:
		m.append((i, i + 1))
	else:
		m.append((n, 1))
c = 1
copy = n
while prime(copy) == False:
	m.append((c, n - c))
	c += 1
	copy += 1
	if c > n:
		c %= n
print(len(m))
for i in m:
	print(*i)


n = int(input())
N = n * n
a = [1] * (N + 1)
a[1] = 0
i = 2
while i <= N:
	if a[i] == 1:
		j = 2 * i
		while j <= N:
			a[j] = 0
			j += i
	i += 1
k = n
while a[k] == 0:
	k += 1
print(k)
for i in range(1, n + 1):
	if i < n:
		print(i, i + 1)
	if i == n:
		print(i, 1)
now = 1
for i in range(k - n):
	if now + 2 <= n:
		print(now, now + 2)
	else:
		print(now, now + 2 - n)
	if now % 2 == 1:
		now += 1
	else:
		now += 3


def check(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
n = int(input())
if n <= 2:
	exit(print(-1))
ans = []
for i in range(n):
	ans.append((i + 1, (i + 1) % n + 1))
for i in range(1, n // 2 + 1):
	if check(len(ans)):
		print(len(ans))
		for i in ans:
			print(i[0], i[1])
		exit(0)
	ans.append((i, i + n // 2))
print(-1)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
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')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def primeN(n):
	prime = [True for i in range(n + 1)]
	prime[0] = False
	prime[1] = False
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return [p for p in range(n + 1) if prime[p]]
for _ in range(1):
	n = Int()
	pr = primeN(2000)
	edges = pr[bisect_left(pr, n)]
	ans = [(1, n)]
	need = edges - n
	over = set()
	for i in range(1, n + 1):
		if need and i not in over and (i + 2 not in over):
			ans.append((i, i + 2))
			over.add(i)
			over.add(i + 2)
			need -= 1
	for i in range(n - 1):
		ans.append((i + 1, i + 2))
	print(len(ans))
	for i in ans:
		print(*i)


from sys import stdin, stdout, setrecursionlimit
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nlargest
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm, accumulate
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
setrecursionlimit(10 ** 9)
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return input()

def num():
	return int(input())

def L():
	return list(sp())

def LF():
	return list(spf())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def spf():
	return map(int, input.readline().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def pmat2(A):
	for ele in A:
		for j in ele:
			print(j, end='')
		print()

def iseven(n):
	return n % 2 == 0

def seive(r):
	prime = [1 for i in range(r + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(r + 1):
		if prime[i]:
			for j in range(2 * i, r + 1, i):
				prime[j] = 0
	return prime

def isprime(x):
	if x == 2:
		return True
	elif x % 2 == 0:
		return False
	sq = int(sqrt(x)) + 1
	for i in range(3, sq, 2):
		if x % i == 0:
			return False
	return True
n = int(input())
m = n
while not isprime(m):
	m += 1
print(m)
print(1, n)
for i in range(n - 1):
	print(i + 1, i + 2)
for i in range(m - n):
	print(i + 1, i + 1 + n // 2)
endtime = time.time()


import bisect

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	ans = []
	for i in range(n + 1):
		if prime[i]:
			ans.append(i)
	return ans
n = int(input())
prime = SieveOfEratosthenes(1009)
if n in prime:
	print(n)
	for i in range(1, n):
		print(i, i + 1)
	print(n, 1)
else:
	j = bisect.bisect_left(prime, n)
	print(prime[j])
	for i in range(1, n):
		print(i, i + 1)
	print(n, 1)
	for i in range(1, prime[j] - n + 1):
		print(i, n - i)


from math import sqrt
n = int(input())

def prost(n):
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
f = n
while not prost(f):
	f += 1
print(f)
for i in range(1, n):
	print(i, i + 1)
print(n, 1)
g = 1
f = f - n
while f:
	print(1 + g - 1, n - g)
	g += 1
	f -= 1


import sys
input = lambda : sys.stdin.readline().strip()
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999]
d = {}
visited = {}
for i in range(1, 2001):
	d[i] = False
	visited[i] = False
for i in primes:
	d[i] = True
n = int(input())
res = []
for i in range(1, n):
	res.append((i, i + 1))
res.append((n, 1))
cur = 1
while not d[len(res)]:
	if not visited[cur]:
		res.append((cur, cur + 2))
		visited[cur] = True
		visited[cur + 2] = True
	cur += 1
print(len(res))
for i in res:
	print(i[0], i[1])


def binarySearch(left, right, n, primes):
	if left <= right:
		mid = int((left + right) / 2)
		if mid == 0 or mid == len(primes) - 1:
			return mid
		if primes[mid] == n:
			return mid - 1
		if primes[mid] < n and primes[mid + 1] > n:
			return mid
		if n < primes[mid]:
			return binarySearch(left, mid - 1, n, primes)
		else:
			return binarySearch(mid + 1, right, n, primes)
	return 0

def prime(a):
	return all((a % i for i in range(2, a)))

def plist(start, end):
	start = 2
	end = 2000
	l = []
	for val in range(start, end + 1):
		if val > 1:
			for n in range(2, val):
				if val % n == 0:
					break
			else:
				l.append(val)
	return l

def printc(n):
	for k in range(1, n):
		print(k, k + 1)
	print(k + 1, 1)

def printck(n, tn):
	op1 = tn // 2 + 1
	print(1, op1)
	for k in range(2, n + 1):
		print(k, op1 + 1)
		op1 = op1 + 1
n = eval(input())
c = prime(n)
l = plist(0, 2000)
if c:
	print(n)
	printc(n)
else:
	nearest = binarySearch(0, len(l) - 1, n, l)
	fin = l[nearest + 1]
	diff = fin - n
	print(n + diff)
	printc(n)
	printck(diff, n)


def isp(x):
	for i in range(2, int(x ** 0.5) + 1):
		if not x % i:
			return 0
	return 1

def nxtp(x):
	p = x
	while not isp(p):
		p += 1
	return p
n = int(input())
k = nxtp(n)
print(k)
for i in range(n):
	print(i + 1, i + 2 if i + 2 != n + 1 else 1)
r = k - n
for i in range(r):
	print(i + 1, i + 1 + n // 2)


import bisect

def primelist(n):
	l = [1] * (n + 1)
	l[0] = l[1] = 0
	v = int(n ** 0.5) + 1
	for i in range(2, v + 1):
		if l[i]:
			for j in range(i * i, n, i):
				l[j] = 0
	return [i for i in range(n) if l[i] == 1]
primes = primelist(2000)
n = int(input())
m = primes[bisect.bisect_left(primes, n)]
print(m)
for i in range(n):
	if i + 2 > n:
		print(i + 1, 1)
	else:
		print(i + 1, i + 2)
left = m - n
i = 1
while left:
	print(i, i + n // 2)
	left -= 1
	i += 1


n = int(input())

def prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			return 0
	return 1
ans = n
while prime(ans) == 0:
	ans += 1
print(ans)
for i in range(1, n):
	print(i, i + 1)
print(1, n)
for i in range(1, ans - n + 1):
	print(i, i + n // 2)


n = int(input())
if n < 3:
	print(-1)
else:
	prime = [1 for i in range(2001)]
	p = 2
	while p * p <= 2000:
		if prime[p] == True:
			for i in range(p * p, 2001, p):
				prime[i] = 0
		p += 1
	length = n
	for i in range(n, 2001):
		if prime[i] == 1:
			length = i
			break
	print(length)
	for i in range(n - 1):
		print(i + 1, i + 2)
	print(n, 1)
	for i in range(length - n):
		print(i + 1, i + 1 + n // 2)


def prime(n):
	for i in range(2, n):
		if n % i == 0:
			return False
	else:
		return True
n = int(input())
e = []
for i in range(n):
	e += [[i, (i + 1) % n]]
x = n
a = 0
b = x // 2
while prime(x) != True:
	e += [[a, b]]
	a += 1
	b += 1
	x += 1
print(x)
for i in e:
	print(i[0] + 1, i[1] + 1)


def prime(n):
	l = [-1] * n
	visited = [False] * n
	visited[0] = True
	visited[1] = True
	p = 2
	while p * p < n:
		if visited[p] == False:
			for i in range(p * p, n, p):
				l[i] = p
				visited[i] = True
		p += 1
	d = []
	for i in range(n):
		if not visited[i]:
			d.append(i)
	return d

def binary(k, n, primes):
	start = 0
	last = n
	j = 0
	while start < last:
		mid = (start + last) // 2
		if primes[mid] == k:
			return mid
		elif primes[mid] > k:
			last = mid
			j = last
			if primes[last] > k and primes[last - 1] < k:
				return last
		else:
			start = mid + 1
			j = start
			if primes[start] < k and primes[start + 1] > k:
				return start + 1
	return j
n = int(input())
primes = prime(1013)
t = binary(n, len(primes) - 1, primes)
print(primes[t])
count = 0
for i in range(n):
	print(i % (n + 1) + 1, (i + 1) % n + 1)
	count += 1
for i in range(primes[t] - count):
	print(i + 1, i + 1 + n // 2)
	count += 1


from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))
sieve = [1] * 2001
for i in range(2, 35):
	if sieve[i]:
		for q in range(2 * i, 2001, i):
			sieve[q] = 0
primes = [p for p in range(2, 2001) if sieve[p]]
primeset = set(primes)

def solve():
	n = ri()
	m = n
	edges = []
	for i in range(1, n):
		edges.append([i, i + 1])
	edges.append([n, 1])
	(u, v) = (1, n // 2 + 1)
	while m not in primeset:
		m += 1
		edges.append([u, v])
		u += 1
		v += 1
	print(m)
	for edge in edges:
		print(*edge)
mode = 's'
if mode == 'T':
	t = ri()
	for i in range(t):
		solve()
else:
	solve()


def is_prime(x):
	if x == 2 or x == 3:
		return True
	elif x < 2 or x % 2 == 0:
		return False
	else:
		for i in range(3, x, 2):
			if i * i > x:
				return True
			if x % i == 0:
				return False
n = int(input())
es = []
for i in range(n):
	es.append((i, (i + 1) % n))
np = n
while not is_prime(np):
	np += 1
i = 0
for j in range(n, np):
	es.append((i, i + 2))
	i += 1
	if i % 2 == 0 and i % 4 != 0:
		i += 2
print(len(es))
for e in es:
	print(e[0] + 1, e[1] + 1)


def seiveOfEratosthenes(n):
	prime = [1 for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == 1:
			for i in range(p * p, n + 1, p):
				prime[i] = 0
		p += 1
	return prime
n = int(input())
prime = seiveOfEratosthenes(1500)
n1 = n
while n1 <= n + n // 2:
	if prime[n1] == 1:
		break
	else:
		n1 += 1
print(n1)
for i in range(1, n):
	print(i, i + 1)
print(n, 1)
n1 -= n
x = 1
y = 3
while n1 > 0:
	print(x, y)
	x += 1
	y += 1
	if x % 2 != 0:
		x += 2
		y += 2
	if x > n:
		x = 1
	if y > n:
		y = 1
	n1 -= 1


from collections import defaultdict
hash = defaultdict(list)
n = int(input())
from math import sqrt

def is_prime(n):
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
primes = set()
for i in range(2, 10 ** 5):
	if is_prime(i):
		primes.add(i)
for i in range(n):
	(a, b) = ((i + 1) % n, (i - 1) % n)
	a += 1
	b += 1
	hash[i + 1].append(a)
	hash[i + 1].append(b)
total = n
seti = set()
if n in primes:
	print(total)
	for i in hash.keys():
		for j in hash[i]:
			if (j, i) not in seti:
				print(i, j)
				seti.add((i, j))
else:
	popi = set()
	for i in range(1, n + 1):
		if total in primes:
			print(total)
			break
		if i not in popi:
			hash[i].append((i + 1) % n + 1)
			popi.add((i + 1) % n + 1)
			total += 1
	for i in hash.keys():
		for j in hash[i]:
			if (j, i) not in seti:
				print(i, j)
				seti.add((i, j))


def get_prime_list(ub):
	from itertools import chain
	from math import sqrt
	(ub_sqrt, is_prime) = (int(sqrt(ub)) + 1, [0, 0, 1, 1] + [0] * (ub - 3))
	if ub < 4:
		return is_prime[:ub + 1]
	is_prime[5::6] = [1] * ((ub + 1) // 6)
	is_prime[7::6] = [1] * ((ub - 1) // 6)
	for n in chain(range(5, ub_sqrt, 6), range(7, ub_sqrt, 6)):
		if is_prime[n]:
			is_prime[n * 3::n * 2] = [0] * ((ub - n) // (n * 2))
	return is_prime
primes = get_prime_list(1009)
N = int(input())
ans = [f'{i} {i + 1}' for i in range(1, N)] + [f'1 {N}']
edge_count = N
(i, half) = (1, N // 2)
while not primes[edge_count]:
	ans.append(f'{i} {i + half}')
	i += 1
	edge_count += 1
print(edge_count)
print(*ans, sep='\n')


from bisect import *

def era(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n ** 0.5) * 1):
		if not is_prime[i]:
			continue
		for j in range(2 * i, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
n = int(input())
primes = era(1500)
idx = bisect_left(primes, n)
p = primes[idx]
print(p)
for i in range(n):
	if i < n - 1:
		print(i + 1, i + 2)
	else:
		print(n, 1)
for i in range(p - n):
	print(i + 1, i + 1 + n // 2)


import math

def function(n):
	prime_nums = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049]
	result = []
	p = 0
	q = 1
	for i in range(0, 10 ** 9):
		p += 1
		q += 1
		if p > n:
			break
		result.append([p, q])
	result[-1][-1] = 1
	if len(result) in prime_nums:
		print(len(result))
		for j in result:
			print(*j)
	else:
		m1 = len(result)
		total = 0
		m2 = 0
		for j in prime_nums:
			if j > m1:
				m2 = j
				break
		total = m2 - m1
		for k in range(total):
			result.append([k + 1, k + 1 + int(n / 2)])
		print(len(result))
		for m in result:
			print(*m)
n = int(input())
function(n)


from sys import stdout
prime = list(map(int, '2\t3\t5\t7\t11\t13\t17\t19\t23\t29\t31\t37\t41\t43\t47\t53\t59\t61\t67\t71 73\t79\t83\t89\t97\t101\t103\t107\t109\t113\t127\t131\t137\t139\t149\t151\t157\t163\t167\t173 179\t181\t191\t193\t197\t199\t211\t223\t227\t229\t233\t239\t241\t251\t257\t263\t269\t271\t277\t281 283\t293\t307\t311\t313\t317\t331\t337\t347\t349\t353\t359\t367\t373\t379\t383\t389\t397\t401\t409 419\t421\t431\t433\t439\t443\t449\t457\t461\t463\t467\t479\t487\t491\t499\t503\t509\t521\t523\t541 547\t557\t563\t569\t571\t577\t587\t593\t599\t601\t607\t613\t617\t619\t631\t641\t643\t647\t653\t659 661\t673\t677\t683\t691\t701\t709\t719\t727\t733\t739\t743\t751\t757\t761\t769\t773\t787\t797\t809 811\t821\t823\t827\t829\t839\t853\t857\t859\t863\t877\t881\t883\t887\t907\t911\t919\t929\t937\t941 947\t953\t967\t971\t977\t983\t991\t997\t1009'.split()))
n = int(input())
p_i = 0
while prime[p_i] < n:
	p_i += 1
stdout.write(str(prime[p_i]) + '\n')
for i in range(n):
	stdout.write(str(i + 1) + ' ' + str((i + 1) % n + 1) + '\n')
for i in range(prime[p_i] - n):
	stdout.write(str(i + 1) + ' ' + str((i + n // 2) % n + 1) + '\n')


import math
n = int(input())

def isprime(x):
	if x < 2:
		return False
	for i in range(2, int(math.sqrt(x)) + 1):
		if x % i == 0:
			return False
	return True
m = n
edges = [(i, i + 1) for i in range(1, n)] + [(n, 1)]
i = 1
while not isprime(m):
	m += 1
	edges.append((i, i + n // 2))
	i += 1
print(len(edges))
for i in edges:
	print(*i)


import math as mt
import sys, string, bisect
input = sys.stdin.readline
from collections import deque, defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())

def prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
n = I()
if prime(n):
	print(n)
	for i in range(n - 1):
		print(i + 1, i + 2)
	print(n, 1)
else:
	x = n + 1
	if x % 2 == 0:
		x += 1
	while not prime(x):
		x += 2
	print(x)
	for i in range(n - 1):
		print(i + 1, i + 2)
	print(n, 1)
	c = x - n
	vertex = 1
	i = n - 1
	while c != 0:
		print(vertex, i)
		c -= 1
		if c == 0:
			break
		vertex += 1
		i -= 1


import sys

class DPrimeGraph:

	def solve(self):
		prime = [True] * (10 ** 5 + 1)

		def sieve():
			for i in range(2, int(len(prime) ** 0.5) + 1):
				if not prime[i]:
					continue
				m = 2
				while m * i < len(prime):
					prime[m * i] = False
					m += 1
		sieve()
		n = int(input())
		if n == 3:
			print(3)
			print(1, 2)
			print(2, 3)
			print(3, 1)
			return
		ans = []
		r = 0
		while not prime[n + r]:
			r += 1
		assert r <= n // 2
		for i in range(1, n):
			ans.append((i, i + 1))
		ans.append((n, 1))
		k = 0
		cur = 1
		while k < r:
			assert cur < n + 1 - cur
			ans.append((cur, n - cur))
			cur += 1
			k += 1
		print(len(ans))
		for c in ans:
			print(*c)
solver = DPrimeGraph()
input = sys.stdin.readline
solver.solve()


import sys
input = sys.stdin.readline
write = lambda x: sys.stdout.write(f'{x}\n')

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
n = int(input())
if n == 8:
	print(11)
	for i in range(1, n):
		print(i, i + 1)
	print(1, 8)
	print(2, 4)
	print(2, 5)
	print(2, 6)
	exit()
k = 0
while not is_prime(n + k):
	k += 1
ans = []
for i in range(1, n):
	ans.append((i, i + 1))
if k == 0:
	ans.append((1, n))
elif k == 1:
	ans.append((1, 3))
	ans.append((n - 2, n))
elif k >= 2:
	ans.append((1, 3))
	ans.append((n - 2, n))
	k -= 2
	i = 4
	j = 6
	while k >= 0:
		ans.append((i, j))
		i += 3
		j += 3
		k -= 1
print(len(ans))
for (i, j) in ans:
	print(i, j)


import sys
import math
from collections import Counter
from operator import itemgetter
import queue

def IO():
	sys.stdin = open('pyinput.txt', 'r')
	sys.stdout = open('pyoutput.txt', 'w')

def GCD(a, b):
	if b == 0:
		return a
	else:
		return GCD(b, a % b)

def LCM(a, b):
	return a * (b // GCD(a, b))

def scan(TYPE_1, TYPE_2=0):
	if TYPE_1 == int:
		return map(int, sys.stdin.readline().strip().split())
	elif TYPE_1 == float:
		return map(float, sys.stdin.readline().strip().split())
	elif TYPE_1 == list and TYPE_2 == float:
		return list(map(float, sys.stdin.readline().strip().split()))
	elif TYPE_1 == list and TYPE_2 == int:
		return list(map(int, sys.stdin.readline().strip().split()))
	elif TYPE_1 == str:
		return sys.stdin.readline().strip()
	else:
		print('ERROR!!!!')

def prime(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True

def main():
	n = int(input())
	m = n
	while prime(m) == False:
		m += 1
	print(m)
	for i in range(1, n):
		print(i, i + 1)
	print(1, n)
	m = m - n
	for i in range(2, m + 2):
		print(i, n)
		n -= 1
main()


def prime(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True
n = int(input())
ans = [(i, i + 1) for i in range(1, n)] + [(n, 1)]
next_prime = 0
for j in range(n, 1000000):
	if prime(j):
		next_prime = j
		break
need = next_prime - n
for i in range(1, need + 1):
	next = i + n // 2
	next %= n + 1
	if next == 0:
		next += 1
	ans.append((i, next))
print(len(ans))
for x in ans:
	print(*x)


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

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

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

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
n = iinp()
c = 1
ansl = []
for i in range(1, n):
	ansl.append((i, i + 1))
	c += 1
ansl.append((n, 1))
i = 1
while not isprime(c):
	ansl.append((i, i + 2))
	if i % 4 == 1:
		i += 1
	else:
		i += 3
	c += 1
print(len(ansl))
for i in ansl:
	print(*i)


import math, sys

def isprime(x):
	for d in range(2, int(math.sqrt(x)) + 1):
		if x % d == 0:
			return False
	return True
n = int(input())
edges = []
for x in range(n):
	edges.append((x, (x + 1) % n))
m = n
i = 0
while not isprime(m):
	edges.append((i, n - 2 - i))
	i += 1
	m += 1
print(m)
for (u, v) in edges:
	print(u + 1, v + 1)


n = int(input())
maxa = 1100
parr = [0 for i in range(maxa + 1)]
curp = 2
st = curp ** 2
ind = 0
while True:
	while st + ind * curp <= maxa:
		parr[st + ind * curp] = 1
		ind += 1
	flag = 0
	for i in range(curp + 1, maxa + 1):
		if parr[i] == 0:
			curp = i
			st = curp ** 2
			ind = 0
			flag = 1
			break
	if flag == 0:
		break
parr[0] = 1
parr[1] = 1
for i in range(n, maxa):
	if parr[i] == 0:
		nexp = i
		break
print(nexp)
for i in range(1, n):
	print(i, i + 1)
print(n, 1)
diff = nexp - n
curr = 1
for i in range(diff):
	print(curr, curr + 2)
	if curr % 2 == 0:
		curr += 3
	else:
		curr += 1


M = 10 ** 5 + 2
prime = [0] * M
for i in range(2, M):
	if prime[i]:
		continue
	for j in range(i, M, i):
		if not prime[j]:
			prime[j] = i
N = int(input())
Edge = [(i, i + 1) for i in range(1, N)] + [(1, N)]
D = N
Nh = N // 2
cnt = 1
while prime[D] != D:
	D += 1
	Edge.append((cnt, cnt + Nh))
	cnt += 1
print(len(Edge))
for e in Edge:
	print(*e)


from bisect import bisect_left

def is_prime(n):
	for i in range(2, n):
		if n % i == 0:
			return False
	return True
primes = []
for i in range(2, 1010):
	if is_prime(i):
		primes.append(i)
n = int(input())
adjacencyList = []
for i in range(n):
	adjacencyList.append({(i + 1) % n, (i - 1) % n})
nextPrime = primes[bisect_left(primes, n)]
moreEdges = nextPrime - n
for i in range(moreEdges):
	adjacencyList[i].add(n // 2 + i)
	adjacencyList[n // 2 + i].add(i)
print(nextPrime)
for (i, v) in enumerate(adjacencyList):
	for u in v:
		if u > i:
			print('{} {}'.format(i + 1, u + 1))


import math

def is_prime(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
n = int(input())
l = []
z = n
while not is_prime(z):
	z += 1
print(z)
for i in range(n):
	x = i + 1
	y = x + 1
	if x == n:
		y = 1
	print(x, y)
i = 1
while z - n:
	if i not in l:
		print(i, i + 2)
		z -= 1
		l.append(i)
		l.append(i + 2)
	i += 1


nre = int(input())
dpdfdjf = []
for i in range(nre - 1):
	dpdfdjf.append([i + 1, i + 2])
dpdfdjf.append([nre, 1])
kre = nre

def plotttt(xre):
	i = 2
	while i ** 2 <= xre:
		if xre % i == 0:
			return False
		i += 1
	return True
plotttts = [0] * 50000
for i in range(50000):
	plotttts[i] = 1 if plotttt(i) else 0
wre = (nre + 2) // 2
mre = 1
while wre <= nre:
	if plotttts[kre] == 1:
		break
	else:
		dpdfdjf.append([mre, wre])
		mre += 1
		wre += 1
		kre += 1
print(len(dpdfdjf))
for i in range(len(dpdfdjf)):
	print(dpdfdjf[i][0], dpdfdjf[i][1])


import sys
read = lambda : sys.stdin.readline().strip()
readi = lambda : map(int, read().split())
from collections import *
n = int(read())
nearestPrime = None
for i in range(n, 1010):
	for j in range(2, int(i ** 0.5) + 1):
		if i % j == 0:
			break
	else:
		nearestPrime = i
		break
print(nearestPrime)
for i in range(1, n):
	print(i, i + 1)
print(n, 1)
for i in range(1, nearestPrime - n + 1):
	print(i, n // 2 + i)


def Input():
	tem = input().split()
	ans = []
	for it in tem:
		ans.append(int(it))
	return ans
n = Input()[0]
vis = [0 for i in range(100100)]
biao = []
for i in range(2, 100100):
	if vis[i] == 0:
		biao.append(i)
		cnt = i
		while cnt < 100100:
			vis[cnt] = 1
			cnt += i
m = len(biao)
if n < 3:
	print(-1)
else:
	edge = n
	(l, r) = (0, m - 1)
	while l < r:
		mid = (l + r) // 2
		if biao[mid] < edge:
			l = mid + 1
		elif biao[mid] > edge:
			r = mid
		else:
			l = mid
			break
	target = biao[l]
	print(target)
	for i in range(n):
		print(i + 1, (i + 1) % n + 1)
	(i, j) = (0, 2)
	while edge < target:
		print((i + 1) % n + 1, (j + 1) % n + 1)
		edge += 1
		i = (i - 1 + n) % n
		j = (j + 1) % n


from bisect import *
l = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109]
z = [1, 2, 5, 6, 9, 10, 13, 14, 17, 18, 21, 22, 25, 26, 29, 30, 33, 34, 37, 38]
x = [3, 4, 7, 8, 11, 12, 15, 16, 19, 20, 23, 24, 27, 28, 31, 32, 35, 36, 39, 40]
n = int(input())
idx = bisect_left(l, n)
rem = l[idx] - n
ans = []
for i in range(1, n):
	ans.append([i, i + 1])
ans.append([1, n])
for i in range(1, rem + 1):
	ans.append([z[i - 1], x[i - 1]])
print(len(ans))
for i in ans:
	print(*i)


n = int(input())

def check(k):
	if k == 1:
		return False
	elif k < 4:
		return True
	for i in range(2, int(k ** 0.5) + 1):
		if k % i == 0:
			return False
	return True

def solve(x, n):
	vis = [0] * (n + 1)
	x -= n
	for i in range(1, n):
		print(i, i + 1)
	print(n, 1)
	mid = n // 2 + 1
	for i in range(x):
		print(1 + i, mid + i)
for i in range(n, 2000):
	if check(i):
		print(i)
		solve(i, n)
		break


import math
import sys
from collections import Counter

def getdict(n):
	d = {}
	if type(n) is list:
		for i in n:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	else:
		for i in range(n):
			t = ii()
			if t in d:
				d[t] += 1
			else:
				d[t] = 1
	return d

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

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

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

def sieve(n):
	pr = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			pr.append(p)
	return pr
n = ii()
if n <= 2:
	print(-1)
	exit()
ans = []
for i in range(1, n):
	ans.append(f'{i} {i + 1}')
ans.append(f'{n} {1}')
pr = sieve(n + n // 2 + 1)
t = 0
for i in pr:
	if i >= n:
		t = i
		break
dif = t - n
i = 1
rd = n // 2
while dif > 0:
	ans.append(f'{i} {i + rd}')
	i += 1
	dif -= 1
print(len(ans))
print('\n'.join(ans))


def isPrime(x):
	for a in range(2, int(x ** 0.5) + 1):
		if x % a == 0:
			return False
	return True
n = int(input())
lines = []
for i in range(1, n):
	lines.append(str(i) + ' ' + str(i + 1))
lines.append(str(n) + ' ' + str(1))
currentVal = 1
while not isPrime(len(lines)):
	lines.append(str(currentVal) + ' ' + str(n - currentVal))
	currentVal += 1
print(len(lines))
for i in lines:
	print(i)


from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf
import math

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

def fun(x):
	return sum((int(i) for i in str(x)))

def find(n):
	if n == 3:
		return 3
	while 1:
		flag = 0
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				n += 1
				break
			if i == int(sqrt(n)):
				flag = 1
				break
		if flag:
			break
	return n
t = 1
for _ in range(t):
	n = int(input())
	edges = find(n)
	print(edges)
	for i in range(n):
		if i == n - 1:
			print(1, n)
		else:
			print(i + 1, i + 2)
	for i in range(edges - n):
		print(i + 1, i + (n + 1) // 2 + 1)


n = int(input())

def pr(x):
	for i in range(2, x):
		if x % i == 0:
			return False
	return True
e = []
for i in range(n):
	e += [[i, (i + 1) % n]]
x = n
u = 0
v = n // 2
while not pr(x):
	e += [[u, v]]
	x += 1
	u += 1
	v += 1
print(x)
for g in e:
	print(g[0] + 1, g[1] + 1)


def isSimple(num):
	n = int(num ** 0.5) + 2
	for i in range(2, n):
		if num % i == 0:
			return False
	return True
n = int(input())
if n == 3:
	print(3)
	print(1, 2)
	print(1, 3)
	print(2, 3)
elif n == 4:
	print(5)
	print(1, 2)
	print(1, 3)
	print(2, 3)
	print(2, 4)
	print(3, 4)
elif n == 5:
	print(7)
	print(1, 2)
	print(1, 3)
	print(2, 3)
	print(2, 4)
	print(3, 4)
	print(1, 5)
	print(4, 5)
elif n == 7:
	print(11)
	print(1, 2)
	print(1, 3)
	print(1, 4)
	print(1, 5)
	print(1, 6)
	print(7, 2)
	print(7, 3)
	print(7, 4)
	print(7, 5)
	print(7, 6)
	print(2, 3)
else:
	num = 0
	n2 = n
	while n2 != 3 and n2 != 8 and (n2 != 4):
		n2 -= 3
		num += 1
	num2 = 0
	num4 = 0
	if n2 == 3:
		num += 1
		num2 = num * 3
	else:
		num4 = n2 // 4
		num2 = num * 3 + num4 * 5
	num3 = num2
	while not isSimple(num3):
		num3 += 1
	print(num3)
	for i in range(num):
		print(i * 3 + 1, i * 3 + 2)
		print(i * 3 + 1, i * 3 + 3)
		print(i * 3 + 2, i * 3 + 3)
	if num4 == 1:
		x = num * 3
		print(x + 1, x + 2)
		print(x + 1, x + 3)
		print(x + 2, x + 3)
		print(x + 2, x + 4)
		print(x + 3, x + 4)
	elif num4 == 2:
		x = num * 3
		print(x + 1, x + 2)
		print(x + 1, x + 3)
		print(x + 2, x + 3)
		print(x + 2, x + 4)
		print(x + 3, x + 4)
		x = num * 3 + 4
		print(x + 1, x + 2)
		print(x + 1, x + 3)
		print(x + 2, x + 3)
		print(x + 2, x + 4)
		print(x + 3, x + 4)
	num5 = 0
	num6 = 0
	for i in range(num3 - num2):
		print(i + 1 + num6, i + num6 + 4)
		num5 += 1
		if num5 == 3:
			num5 = 0
			num6 += 3


from math import sqrt
n = int(input())

def prime(m):
	if m < 2:
		return False
	for k in range(2, int(sqrt(m)) + 1):
		if m % k == 0:
			return False
	return True
ans = 0
for k in range(n, n + 1 + n // 2):
	if prime(k):
		ans = k
		break
if ans == 0:
	print(-1)
else:
	print(ans)
	print(1, n)
	for i in range(n - 1):
		print(i + 1, i + 2)
	for r in range(n, k):
		print((r + 1 - n) % (n + 1), (n // 2 + r + 1 - n) % (n + 1))


import sys
n = int(sys.stdin.readline().strip())
P = []
i = 2
v = True
while v == True:
	w = True
	for p in P:
		if i % p == 0:
			w = False
	if w == True:
		P.append(i)
		if i >= n:
			v = False
			e = i
	i = i + 1
E = [[1, n]]
for i in range(0, n - 1):
	E.append([i + 1, i + 2])
m = n
i = 0
while e > m:
	E.append([i + 1, i + 1 + n // 2])
	m = m + 1
	i = i + 1
print(len(E))
for i in range(0, len(E)):
	print(str(E[i][0]) + ' ' + str(E[i][1]))


import sys
from math import *
from fractions import gcd
readints = lambda : map(int, input().strip('\n').split())

def isprime(x):
	for i in range(2, x):
		if x % i == 0:
			return False
	return True
primes = [2]
for i in range(3, 1111):
	if isprime(i):
		primes.append(i)
primes = set(primes)
n = int(input())
if n in primes:
	print(n)
	for i in range(1, n):
		print(i, i + 1)
	print(n, 1)
else:
	edges = []
	for i in range(1, n):
		edges.append((i, i + 1))
	edges.append((n, 1))
	deg = {}
	from collections import defaultdict as dd
	g = dd(set)
	for i in range(2, n):
		g[i].add(i - 1)
		g[i].add(i + 1)
	g[1].add(2)
	g[1].add(n)
	g[n].add(1)
	g[n].add(n - 1)
	while len(edges) not in primes:
		for i in range(1, n + 1):
			if len(edges) in primes:
				break
			for j in range(i + 1, n + 1):
				if len(g[i]) == 2 and len(g[j]) == 2 and (i not in g[j]) and (j not in g[i]):
					edges.append((i, j))
					g[i].add(j)
					g[j].add(i)
					break
	print(len(edges))
	for e in edges:
		print(e[0], e[1])


n = int(input())
odp = []
for i in range(n - 1):
	odp.append([i + 1, i + 2])
odp.append([n, 1])
k = n

def prime(x):
	i = 2
	while i ** 2 <= x:
		if x % i == 0:
			return False
		i += 1
	return True
primes = [0] * 50000
for i in range(50000):
	primes[i] = 1 if prime(i) else 0
w = (n + 2) // 2
m = 1
while w <= n:
	if primes[k] == 1:
		break
	else:
		odp.append([m, w])
		m += 1
		w += 1
		k += 1
print(len(odp))
for i in range(len(odp)):
	print(odp[i][0], odp[i][1])


MAX_N = 1010
is_prime = [1] * MAX_N + [-1]
is_prime[0] = is_prime[1] = 0
i = 2
while i < MAX_N:
	for j in range(2 * i, MAX_N, i):
		is_prime[j] = 0
	i += 1
	while is_prime[i] == 0:
		i += 1
n = int(input())
if is_prime[n]:
	print(n)
	print('\n'.join(('%s %s' % (i, i + 1) for i in range(1, n))))
	print(n, 1)
if not is_prime[n]:
	m = n + 1
	while is_prime[m] == 0:
		m += 1
	d = m - n
	print(m)
	print('\n'.join(('%s %s' % (i, i + 1) for i in range(1, n))))
	print(n, 1)
	print('\n'.join(('%s %s\n%s %s' % (i, i + 2, i + 1, i + 3) for i in range(1, 1 + 4 * (d // 2), 4))))
	if d & 1:
		print(n - 2, n)


import math
cc = [0] * 1501
cc[0] = cc[1] = 1
for i in range(2, int(math.sqrt(1501)) + 1):
	if not cc[i]:
		for j in range(i * i, 1501, i):
			cc[j] = 1
n = int(input())
sol = []
for i in range(1, n):
	sol.append((i, i + 1))
sol.append((n, 1))
i = 1
while cc[n]:
	sol.append((i, i + 2))
	n += 1
	i += 1
	if cc[n]:
		sol.append((i, i + 2))
		n += 1
		i += 3
print(n)
for x in sol:
	print(x[0], x[1])


import bisect
pr = [1] * 100000
pr[2] = 1
for i in range(4, 100000, 2):
	pr[i] = 0
i = 3
while i * i < 100000:
	j = 2 * i
	while j < 100000:
		pr[j] = 0
		j += i
	i += 2
prime = []
for i in range(2, 100000):
	if pr[i] == 1:
		prime.append(i)
n = int(input())
if n in prime:
	print(n)
	for i in range(1, n + 1):
		if i < n:
			print(i, ' ', i + 1)
		else:
			print(n, ' ', 1)
else:
	used = [0] * (n + 1)
	p = prime[bisect.bisect_right(prime, n)]
	print(p)
	p = p - n
	for i in range(1, n + 1):
		if i < n:
			print(i, ' ', i + 1)
		else:
			print(n, ' ', 1)
	i = 1
	while p > 0:
		if used[i] == 0:
			print(i, ' ', i + 2)
			used[i] = 1
			used[i + 2] = 1
			p = p - 1
		i = i + 1


d = []
from bisect import *

def siv(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	prev = 0
	for p in range(2, n + 1):
		if prime[p]:
			d.append(p)
siv(10 ** 5)
n = int(input())
z = bisect_left(d, n)
p = d[z] - n
if p > n // 2:
	print(-1)
	exit(0)
print(d[z])
for i in range(n - 1):
	print(i + 1, i + 2)
print(n, 1)
for j in range(p):
	print(j + 1, n - j - 1)


prime = [True] * 1501
prime[0] = False
prime[1] = False
for i in range(2, 1501):
	if prime[i]:
		for j in range(i * i, 1501, i):
			prime[j] = False
n = int(input())
degree = [2] * n
ans = []
edges = n
for i in range(n - 1):
	ans.append([i + 1, i + 2])
ans.append([1, n])
c = 0
while not prime[edges]:
	ans.append([c + 1, c + n // 2 + 1])
	degree[c] += 1
	degree[c + n // 2] += 1
	c += 1
	edges += 1
print(len(ans))
for i in ans:
	print(i[0], i[1])


from sys import stdout
pr = [0] * 10 ** 6
pr[0] = pr[1] = 1
for i in range(2, 10 ** 6):
	if pr[i] == 0:
		for j in range(2 * i, 10 ** 6, i):
			pr[j] = 1
n = int(input())
c = [2] * n
ans = []
for i in range(1, n):
	ans.append([i - 1, i])
ans.append([n - 1, 0])
dis = 2
ed = n
fl = 0
for i in range(n // 2):
	if pr[ed] != 0:
		ans.append([i, i + n // 2])
		ed += 1
	else:
		fl = 1
		break
if fl == 1:
	print(ed)
	for i in ans:
		stdout.write(str(i[0] + 1) + ' ' + str(i[1] + 1) + '\n')
else:
	print(-1)


def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
n = int(input())
m = n
s = []
for i in range(n):
	s.append((i + 1, (i + 1) % n + 1))
i = 1
while not isprime(m):
	m += 1
	s.append((i, i + n // 2))
	i += 1
print(m)
for i in s:
	print(*i)


import math
n = int(input())
degress = [2] * n

def is_prime(x):
	for i in range(2, int(math.sqrt(x)) + 2):
		if x % i == 0:
			return False
	return True
goal = n
while not is_prime(goal):
	goal += 1
print(goal)
result = [(x, x + 1) for x in range(1, n)] + [(1, n)]
for i in range(goal - n):
	degress[i] += 1
	degress[i + n // 2] += 1
	result.append((i + 1, i + n // 2 + 1))
for x in result:
	print(x[0], x[1])


def is_prime(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(n):
	output = ['1 2']
	for i in range(3, n + 1):
		output.append('%d %d' % (i - 1, i))
	output.append('%d %d' % (1, n))
	l = 2
	r = n
	while not is_prime(len(output)):
		if l >= r:
			raise Exception('Noooo')
		output.append('%d %d' % (l, r))
		l += 1
		r -= 1
	print(len(output))
	for o in output:
		print(o)
n = int(input())
solve(n)