from fractions import gcd

def suspect(a, s, d, n):
	x = pow(a, d, n)
	if x == 1:
		return True
	for r in range(s):
		if x == n - 1:
			return True
		x = x * x % n
	return False

def isPrime(n):
	if n <= 1 or (n > 2 and n % 2 == 0):
		return False
	test = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
	d, s = n - 1, 0
	while d % 2 == 0:
		s += 1
		d //= 2
	for a in test:
		if a >= n:
			break
		if not suspect(a, s, d, n):
			return False
	return True

def getNext(n, W, N):
	i, j = (n - 1) // W, (n - 1) % W
	for dy, dx in [(0,1),(1,0),(0,-1),(-1,0)]:
		yy, xx = i + dy, j + dx
		if yy < 0 or xx < 0 or xx >= W:
			continue
		m = yy * W + xx + 1
		if m > N or isPrime(m):
			continue
		yield m

def search(W, N):
	ds = [d for d in range(0,W) if gcd(d,W) != 1]
	vis, dvis = {}, {}
	q = [1]
	vis[1] = True
	h = 0
	while h < len(q):
		n = q[h]
		if n == N:
			return 0
		h += 1
		if gcd(n % W, W) > 1:
			if not n % W in dvis:
#				print("%d: %d, %d" % (W, n % W, n))
				dvis[n % W] =  True
				if len(dvis) == len(ds):
					break
		for m in getNext(n, W, N):
			if not m in vis:
				vis[m] = True
				q.append(m)
	return len(dvis) == len(ds) and 1 or 2

def search2(W, N):
	vis = {}
	q = [N]
	vis[N] = True
	h = 0
	while h < len(q):
		n = q[h]
		if gcd(n % W, W) > 1:
			return True
		h += 1
		for m in getNext(n, W, N):
			if not m in vis:
				vis[m] = True
				q.append(m)
	return False

N = int(input())
W = 2
ok = False
while True:
	if ok:
		break
	res = search(W, N)
	if res == 0:
		break
	if res == 1:
		if search2(W, N):
			break
	W += 1
print(W)