Mr. Funt now lives in a country with a very specific tax laws. The total income of mr. Funt during this year is equal to n (n ≥ 2) burles and the amount of tax he has to pay is calculated as the maximum divisor of n (not equal to n, of course). For example, if n = 6 then Funt has to pay 3 burles, while for n = 25 he needs to pay 5 and if n = 2 he pays only 1 burle.

As mr. Funt is a very opportunistic person he wants to cheat a bit. In particular, he wants to split the initial n in several parts n_1 + n_2 + ... + n_{k} = n (here k is arbitrary, even k = 1 is allowed) and pay the taxes for each part separately. He can't make some part equal to 1 because it will reveal him. So, the condition n_{i} ≥ 2 should hold for all i from 1 to k.

Ostap Bender wonders, how many money Funt has to pay (i.e. minimal) if he chooses and optimal way to split n in parts.


-----Input-----

The first line of the input contains a single integer n (2 ≤ n ≤ 2·10^9) — the total year income of mr. Funt.


-----Output-----

Print one integer — minimum possible number of burles that mr. Funt has to pay as a tax.


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

Output
2

Input
27

Output
3

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
def prime(x):
	y = min(x, int(x ** 0.5) + 2)
	for d in range(2, y):
		if x % d == 0:
			return False
	return True

def solve(n):
	if prime(n):
		return 1
	if n % 2 and prime(n - 2):
		return 2
	return 2 + n % 2
n = int(input())
print(solve(n))


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
int1 = lambda x: int(x) - 1

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def solve():

	def isprime(n):
		n = abs(int(n))
		if n < 2:
			return False
		if n == 2:
			return True
		if not n & 1:
			return False
		for x in range(3, int(n ** 0.5) + 1, 2):
			if n % x == 0:
				return False
		return True
	(n,) = aj()
	if isprime(n):
		print(1)
	elif isprime(n - 2):
		print(2)
	elif n % 2 == 0:
		print(2)
	else:
		print(3)
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
solve()


import os
import sys
from io import BytesIO, IOBase
import math

def isprime(n):
	for x in range(2, math.floor(math.sqrt(n)) + 1):
		if n % x == 0:
			return False
	return True

def main():
	n = int(input())
	if n == 2:
		print(1)
	elif n % 2 == 0:
		print(2)
	elif isprime(n):
		print(1)
	elif isprime(n - 2):
		print(2)
	else:
		print(3)
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')
main()


n = int(input())

def is_prime(m):
	if m <= 1:
		return False
	for i in range(2, int(m ** 0.5) + 1):
		if m % i == 0:
			return False
	return True
if is_prime(n):
	print(1)
elif not n & 1 or is_prime(n - 2):
	print(2)
else:
	print(3)


import sys
import math
import itertools
import collections

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base):
	newnumber = 0
	while number > 0:
		newnumber += number % base
		number //= base
	return newnumber

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 lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def wr(arr):
	return ' '.join(map(str, arr))

def revn(n):
	return str(n)[::-1]

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)
n = ii()
if prime(n):
	print(1)
elif n % 2 == 0 or prime(n - 2):
	print(2)
else:
	print(3)


def prime(n):
	if n == 2:
		return True
	if n < 2 or n % 2 == 0:
		return False
	i = 3
	while i * i <= n:
		if n % i == 0:
			return False
		i += 2
	return True
n = int(input())
if prime(n):
	print(1)
elif n % 2 == 0 or prime(n - 2):
	print(2)
else:
	print(3)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

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

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

def 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
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

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

def li():
	return list(map(int, input().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')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = 1
for _ in range(t):
	n = ii()
	if isPrime(n):
		print(1)
		continue
	if n % 2 == 0 or (n > 2 and isPrime(n - 2) == 1):
		print(2)
	else:
		print(3)


def prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return 0
	return 1
n = int(input())
if prime(n) == 1:
	print(1)
elif n % 2 == 0 or prime(n - 2) == 1:
	print(2)
else:
	print(3)


def isPrime(n):
	if n % 2 == 0:
		return n == 2
	d = 3
	while d * d <= n and n % d != 0:
		d += 2
	return d * d > n
n = int(input())
ans = 0
if isPrime(n):
	ans = 1
elif n % 2 == 0:
	ans = 2
elif isPrime(n - 2):
	ans = 2
else:
	ans = 3
print(ans)


import math

def check_prime(num):
	if all((num % i != 0 for i in range(2, int(math.sqrt(num)) + 1))):
		return 1
	else:
		return 0
ans = 0
n = int(input())
if check_prime(n):
	ans = 1
elif n % 2:
	if check_prime(n - 2):
		ans = 2
	else:
		ans = 3
else:
	ans = 2
print(ans)


from __future__ import division, print_function
from sys import stdin, stdout
import itertools, os, sys, threading
from collections import deque, Counter, OrderedDict, defaultdict
import heapq
from math import ceil, floor, log, sqrt, factorial, pow, pi, gcd
from fractions import Fraction

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

def si():
	return str(input())

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

def li():
	return list(mi())

def fii():
	return int(stdin.readline())

def fsi():
	return str(stdin.readline())

def fmi():
	return map(int, stdin.readline().split())

def fli():
	return list(fmi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[0]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

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

def ntl(n):
	return [int(i) for i in str(n)]

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

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
graph = defaultdict(list)
visited = [0] * 1000000
col = [-1] * 1000000

def dfs(v, c):
	if visited[v]:
		if col[v] != c:
			print('-1')
			exit()
		return
	col[v] = c
	visited[v] = 1
	for i in graph[v]:
		dfs(i, c ^ 1)

def bfs(d, v):
	q = []
	q.append(v)
	visited[v] = 1
	while len(q) != 0:
		x = q[0]
		q.pop(0)
		for i in d[x]:
			if visited[i] != 1:
				visited[i] = 1
				q.append(i)
		print(x)

def make_graph(e):
	d = {}
	for i in range(e):
		(x, y) = mi()
		if x not in d.keys():
			d[x] = [y]
		else:
			d[x].append(y)
		if y not in d.keys():
			d[y] = [x]
		else:
			d[y].append(x)
	return d

def gr2(n):
	d = {}
	for i in range(n):
		(x, y) = mi()
		if x not in d.keys():
			d[x] = [y]
		else:
			d[x].append(y)
	return d

def connected_components(graph):
	seen = set()

	def dfs(v):
		vs = set([v])
		component = []
		while vs:
			v = vs.pop()
			seen.add(v)
			vs |= set(graph[v]) - seen
			component.append(v)
		return component
	ans = []
	for v in graph:
		if v not in seen:
			d = dfs(v)
			ans.append(d)
	return ans

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

def find_all(a_str, sub):
	start = 0
	while True:
		start = a_str.find(sub, start)
		if start == -1:
			return
		yield start
		start += len(sub)

def Prime(x):
	if x < 2:
		return False
	for i in range(2, int(sqrt(x)) + 1):
		if x % i == 0:
			return False
	return True
n = ii()
if Prime(n):
	print(1)
elif n % 2 == 0:
	print(2)
elif Prime(n - 2):
	print(2)
else:
	print(3)


import math
n = int(input())
if n == 2:
	exit(print(1))
if n % 2 == 0:
	print(2)
	exit()
flag = 0
for i in range(2, math.ceil(n ** 0.5) + 1):
	if n % i == 0:
		flag = 1
		break
if flag == 0:
	print(1)
	exit()
else:
	for i in range(2, math.ceil((n - 2) ** 0.5) + 1):
		if (n - 2) % i == 0:
			print(3)
			exit()
	print(2)


def isprime(n):
	n = abs(int(n))
	if n < 2:
		return False
	if n == 2:
		return True
	if not n & 1:
		return False
	for x in range(3, int(n ** 0.5) + 1, 2):
		if n % x == 0:
			return False
	return True
n = int(input())
if isprime(n):
	print(1)
elif isprime(n - 2):
	print(2)
elif n % 2 == 0:
	print(2)
else:
	print(3)


def check_witness(a, n, d, s):
	x = pow(a, d, n)
	if x == 1 or x == n - 1:
		return True
	for r in range(s - 1):
		x = pow(x, 2, n)
		if x == n - 1:
			return True
	return False

def miller_rabin(n):
	wittnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
	if n < 38:
		return n in wittnesses
	d = n - 1
	s = 0
	while d % 2 == 0:
		s += 1
		d //= 2
	for a in wittnesses:
		if not check_witness(a, n, d, s):
			return False
	return True
n = int(input())
if miller_rabin(n):
	print(1)
elif n % 2 == 0:
	print(2)
elif miller_rabin(n - 2):
	print(2)
else:
	print(3)


def check_easy(n):
	flag = True
	for j in range(2, int(n ** 0.5) + 1):
		if n % j == 0:
			flag = False
			break
	return flag

def main():
	n = int(input())
	if check_easy(n):
		print(1)
	elif n % 2 == 0:
		print(2)
	elif check_easy(n - 2):
		print(2)
	else:
		print(3)
main()


def isPrime(num):
	if num <= 1:
		return False
	if num <= 3:
		return True
	if num % 2 == 0 or num % 3 == 0:
		return False
	i = 5
	while i * i <= num:
		if num % i == 0 or num % (i + 2) == 0:
			return False
		i += 6
	return True
n = int(input())
if isPrime(n):
	print(1)
elif n + 1 & 1:
	print(2)
elif isPrime(n - 2):
	print(2)
else:
	print(3)


def p(x):
	for i in range(2, int(x ** 0.5) + 1):
		if x % i == 0:
			return False
	return True
n = int(input())
if p(n):
	print(1)
elif p(n - 2) or n % 2 == 0:
	print(2)
else:
	print(3)


prime = []
l = [0 for i in range(int(100000.0 + 2))]
for i in range(2, int(100000.0)):
	if l[i] == 0:
		prime.append(i)
		j = 1
		while i * j < int(100000.0):
			l[i * j] = 1
			j += 1

def isPrime(val):
	for i in prime:
		if val % i == 0 and i != val:
			return 0
	return 1
n = int(input())
ans = 0
if isPrime(n):
	ans = 1
elif n % 2 == 0:
	ans = 2
elif isPrime(n - 2):
	ans = 2
else:
	ans = 3
print(ans)


import sys
import math

def isprime(n):
	if n == 1:
		return False
	if n == 2:
		return True
	if n == 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(math.sqrt(n)) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def answer(n):
	if isprime(n):
		return 1
	if n % 2 == 0:
		return 2
	if isprime(n - 2):
		return 2
	else:
		return 3

def main():
	n = int(sys.stdin.readline())
	print(answer(n))
	return
main()


def isPrime(num):
	for i in range(2, int(num ** 0.5) + 1):
		if num % i == 0:
			return False
	return True
a = int(input())
x = a
if isPrime(x) == True:
	print(1)
elif x % 2 == 0:
	print(2)
elif isPrime(x - 2) == True:
	print(2)
else:
	print(3)


def primes():
	ps = [2, 3, 5, 7, 11, 13, 17, 19]
	ps_below_sqrt = [2, 3]
	for p in ps:
		yield p
	p = 23
	while True:
		while ps_below_sqrt[-1] * ps_below_sqrt[-1] < p:
			ps_below_sqrt.append(ps[len(ps_below_sqrt)])
		if all((p % q for q in ps_below_sqrt)):
			ps.append(p)
			yield p
		p += 2

def is_prime(n):
	for p in primes():
		if p * p > n:
			return True
		if n % p == 0:
			return False
n = int(input())
if n == 2:
	print(1)
elif n % 2 == 0:
	print(2)
elif is_prime(n):
	print(1)
elif is_prime(n - 2):
	print(2)
else:
	print(3)


def isPrime(n):

	def compositeTry(a, d, n, s):
		if pow(a, d, n) == 1:
			return False
		for i in range(s):
			if pow(a, 2 ** i * d, n) == n - 1:
				return False
		return True
	knownPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
	if n in knownPrimes:
		return True
	if any((n % p == 0 for p in knownPrimes)) or n in (0, 1):
		return False
	(d, s) = (n - 1, 0)
	while not d % 2:
		(d, s) = (d >> 1, s + 1)
	return not any((compositeTry(a, d, n, s) for a in (2, 3, 5, 7)))

def main():
	n = int(input())
	if isPrime(n):
		print(1)
	elif n % 2 == 0:
		print(2)
	elif isPrime(n - 2):
		print(2)
	else:
		print(3)
main()


from sys import stdin, stdout

def prime(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True
n = int(input())
if prime(n) == True:
	print('1')
	exit()
if n == 2:
	print('2')
	exit()
if n == 4:
	print('2')
	exit()
if n % 2 == 0:
	print('2')
elif prime(n - 2) == True:
	print('2')
else:
	print('3')


def is_prime(x):
	for i in range(2, int(x ** 0.5) + 1):
		if x % i == 0:
			return False
	return x != 1
n = int(input())
if is_prime(n):
	print(1)
elif n % 2 == 0:
	print(2)
elif is_prime(n - 2):
	print(2)
else:
	print(3)


from math import *

def IsPrime(n):
	for i in range(2, ceil(sqrt(n)) + 1):
		if not n % i:
			return False
	return True
n = int(input())
if IsPrime(n) or n == 2:
	print(1)
elif not n % 2:
	print(2)
elif IsPrime(n - 2):
	print(2)
else:
	print(3)


def prime(x):
	p = int(n ** 0.5)
	p += 2
	for i in range(3, p, 2):
		if x % i == 0:
			return False
	return True

def func(n):
	if n % 2 == 0:
		if n == 2:
			return 1
		return 2
	if n == 1 or n == 3 or n == 5:
		return 1
	if prime(n):
		return 1
	if prime(n - 2):
		return 2
	return 3
n = int(input())
ans = func(n)
print(ans)


def prime(n):
	f = 1
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			f = 0
			break
	return f
n = int(input())
if n == 2:
	print(1)
	exit()
if n % 2 == 0:
	print(2)
	exit()
s = prime(n)
if s == 1:
	print(1)
	exit()
else:
	n = n - 2
	s = prime(n)
	if s == 1:
		print(2)
		exit()
	else:
		print(3)
		exit()


n = int(input())
p = lambda n: 0 if n < 2 else all((n % x for x in range(2, int(n ** 0.5 + 1))))
print(1 if p(n) else 2 if n % 2 == 0 or p(n - 2) else 3)


n = int(input())
import math

def check(n):
	x = math.ceil(math.sqrt(n)) + 1
	for i in range(2, x):
		if n % i == 0:
			return False
	return True
if check(n):
	print(1)
elif n % 2:
	if check(n - 2):
		print(2)
	else:
		print(3)
else:
	print(2 if n != 2 else 1)


from math import sqrt

def prime(n):
	for d in range(3, int(sqrt(n)) + 1, 2):
		if n % d == 0:
			return 0
	return 1
n = int(input())
if n == 2:
	print(1)
elif n % 2 == 0:
	print(2)
elif prime(n):
	print(1)
elif prime(n - 2):
	print(2)
else:
	print(3)


def isprime(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True
n = int(input())
if n > 5 and n % 2:
	if isprime(n):
		print(1)
	elif isprime(n - 2):
		print(2)
	else:
		print(3)
elif n > 2 and (not n % 2):
	print(2)
elif n in (2, 3, 5):
	print(1)


def isPrime(n):
	global primes
	for p in primes:
		if p * p > n:
			return True
		if n % p == 0:
			return False
	return True
erath = [True] * 1000001
erath[0] = False
erath[1] = False
for p in range(2, 1000 + 1):
	if erath[p] == False:
		continue
	for m in range(p * p, 1000000 + 1, p):
		erath[m] = False
primes = [n for n in range(1000000) if erath[n] == True]
money = int(input())
tax = 0
if isPrime(money):
	print(1)
elif money % 2 == 0:
	print(2)
elif isPrime(money - 2):
	print(2)
else:
	print(3)


import random

def probablyPrime(n):
	if n % 2 == 0:
		return False
	s = 0
	d = n - 1
	while True:
		(quotient, remainder) = divmod(d, 2)
		if remainder == 1:
			break
		s += 1
		d = quotient

	def test(r):
		if pow(r, d, n) == 1:
			return False
		for i in range(s):
			if pow(r, 2 ** i * d, n) == n - 1:
				return False
		return True
	for i in range(8):
		r = random.randrange(2, n)
		if test(r):
			return False
	return True
i = int(input())
if i == 2:
	print(1)
elif probablyPrime(i):
	print(1)
elif i % 2 == 0 or probablyPrime(i - 2):
	print(2)
else:
	print(3)


import math

def getLnInput():
	return input().split()

def ceilDivision(a, b):
	return (a - 1) // b + 1

def isPrime(n):
	if n < 1:
		return False
	if n == 2:
		return True
	flg = True
	for i in range(2, math.ceil(math.sqrt(n + 1))):
		if n % i == 0:
			flg = False
			break
	return flg

def main():
	n = int(getLnInput()[0])
	if n < 4:
		print(1)
	elif isPrime(n):
		print(1)
	elif n % 2 == 0:
		print(2)
	elif isPrime(n - 2):
		print(2)
	else:
		print(3)
	return
main()


from math import sqrt

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

def taxes(n):
	if n < 4:
		return 1
	elif n % 2 == 0:
		return 2
	elif prime(n):
		return 1
	elif prime(n - 2):
		return 2
	else:
		return 3
print(taxes(int(input())))


def isPrime(x):
	n = x
	if x >= 2:
		i = 2
		while i * i <= n:
			if x % i == 0:
				return False
			i += 1
		return True
	else:
		return False
cin = input().split()
for k in cin:
	n = int(k)
	count = 0
	if isPrime(n):
		count = 1
	elif isPrime(n - 2) or n % 2 == 0:
		count = 2
	else:
		count = 3
	print(count)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial
from collections import deque

def isprime(x):
	i = 2
	while i * i <= x:
		if x % i == 0:
			return False
		i += 1
	return True
n = int(input())
if n == 2 or n == 3:
	print(1)
elif n % 2 == 0:
	print(2)
elif isprime(n):
	print(1)
elif isprime(n - 2):
	print(2)
else:
	print(3)


x = int(input())
if x % 2 == 0 and x != 2:
	print(2)
	exit(0)

def ip(x):
	if x == 2 or x == 3:
		return 1
	if x == 1 or x % 2 == 0:
		return 0
	n = 3
	while n * n <= x:
		if x % n == 0:
			return 0
		n += 2
	return 1
if ip(x):
	print(1)
	exit(0)
elif x > 2 and ip(x - 2):
	print(2)
	exit(0)
print(3)


import math

def isprime(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
n = int(input())
if isprime(n):
	print(1)
elif n % 2 == 0:
	print(2)
elif n % 2 == 1:
	if isprime(n - 2):
		print(2)
	else:
		print(3)


primes = [2, 3]
x = 3
while x < 200000:
	x += 2
	for i in primes:
		if i * i > x:
			primes.append(x)
			break
		elif x % i == 0:
			break

def is_prime(n):
	for i in primes:
		if i * i > n:
			return True
		if n % i == 0:
			return False
d = {}

def result(n):
	if is_prime(n):
		return 1
	else:
		try:
			return d[n]
		except:
			a = []
			count = 0
			for i in range(n - 2, 0, -1):
				if is_prime(i):
					count += 1
					a.append(i)
				if count > 100:
					break
			a = [result(n - i) for i in a]
			ans = 1 + min(a)
			d[n] = ans
			return ans
n = int(input())
print(result(n))


from sys import stdin
from sys import stdout
from math import ceil
from math import sqrt
n = int(stdin.readline().strip())

def maxPower(num, div):
	power = 0
	while num % div == 0 and n > 1:
		num = num / div
		power += 1
	return power
primes = [2]
ans = 0

def isPrime(n):
	for i in range(2, ceil(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
if n % 2 == 0:
	if n == 2:
		ans = 1
	else:
		ans = 2
else:
	isprime = isPrime(n)
	if isprime:
		ans = 1
	elif isPrime(n - 2):
		ans = 2
	else:
		ans = 3
stdout.write(str(ans))


from math import sqrt

def prime_check(n):
	flag = 1
	for i in range(3, int(sqrt(n)) + 2, 2):
		if n % i == 0:
			flag = 0
			break
	return flag
n = int(input())
arr = [0, 0, 1, 1, 2, 1, 2, 1, 2, 2, 2]
if n <= 10:
	print(arr[n])
elif n % 2 == 0:
	print(2)
elif prime_check(n):
	print(1)
elif prime_check(n - 2):
	print(2)
else:
	print(3)


def Factor(n):
	Ans = []
	d = 2
	while d * d <= n:
		if n % d == 0:
			Ans.append(d)
			n //= d
		else:
			d += 1
	if n > 1:
		Ans.append(n)
	return Ans

def IsPrime(n):
	d = 2
	while d * d <= n and n % d != 0:
		d += 1
	return d * d > n
n = int(input())
ans = 0
k = n
m = n
if IsPrime(n):
	print(1)
elif n % 2 == 0:
	print(2)
else:
	k = n
	while k > 0:
		m = k
		if m % 2 == 0 and m != 2:
			ans += 2
			break
		while not IsPrime(m) or k - m == 1:
			m -= 1
		ans += 1
		k -= m
	print(ans)


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, nsmallest, nlargest
INF = 999999999999999999999999
alphabets = 'abcdefghijklmnopqrstuvwxyz'

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class SegTree:

	def __init__(self, n):
		self.N = 1 << n.bit_length()
		self.tree = [0] * (self.N << 1)

	def update(self, i, j, v):
		i += self.N
		j += self.N
		while i <= j:
			if i % 2 == 1:
				self.tree[i] += v
			if j % 2 == 0:
				self.tree[j] += v
			(i, j) = (i + 1 >> 1, j - 1 >> 1)

	def query(self, i):
		v = 0
		i += self.N
		while i > 0:
			v += self.tree[i]
			i >>= 1
		return v

def SieveOfEratosthenes(limit):
	isPrime = [True] * (limit + 1)
	isPrime[0] = isPrime[1] = False
	primes = []
	for i in range(2, limit + 1):
		if not isPrime[i]:
			continue
		primes += [i]
		for j in range(i * i, limit + 1, i):
			isPrime[j] = False
	return primes

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		n = ri()
		primes = SieveOfEratosthenes(45000)

		def isnprime(n):
			for p in primes:
				if p * p > n:
					break
				if n % p == 0:
					return False
			return True
		if isnprime(n):
			wi(1)
		elif n % 2:
			if isnprime(n - 2):
				wi(2)
			else:
				wi(3)
		else:
			wi(2)
	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()


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

def prime(x):
	for d in range(2, int(ceil(x ** 0.5) + 1)):
		if d < x and x % d == 0:
			return False
	return True
if prime(n):
	print(1)
elif prime(n - 2) or n % 2 == 0:
	print(2)
else:
	print(3)


from sys import *
from math import *

def isPrime(t):
	f = 0
	for i in range(2, int(sqrt(t)) + 1):
		if t % i == 0:
			f = 1
			return False
	return True
t = int(stdin.readline())
if t % 2 == 0 and t != 2:
	print(2)
else:
	f = 0
	m = isPrime(t)
	if m:
		print(1)
	else:
		x = isPrime(t - 2)
		y = isPrime(t - 3)
		if x or y:
			print(2)
		else:
			print(3)


def is_prime(n):
	j = 2
	while j * j <= n:
		if n % j == 0:
			return 0
		j += 1
	return 1

def prob():
	n = int(input())
	if is_prime(n):
		print(1)
	elif n % 2 == 0 or is_prime(n - 2):
		print(2)
	else:
		print(3)
t = 1
for _ in range(0, t):
	prob()


def isprm(x):
	if x == 0 or x == 1:
		return False
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True
n = int(input())
if isprm(n):
	print(1)
elif n % 2 == 0 or isprm(n - 2):
	print(2)
else:
	print(3)


def is_prime(x):
	lst = []
	nn = x
	for i in range(2, round(x ** 0.5) + 1):
		while nn % i == 0:
			nn //= i
			lst.append(i)
	if nn > 1:
		lst.append(nn)
		nn = 1
	return lst
n = int(input())
if n == 2:
	print(1)
	exit(0)
if n == 3:
	print(1)
	exit(0)
if n == 4:
	print(2)
	exit(0)
if n == 5:
	print(1)
	exit(0)
a = is_prime(n)
if len(a) == 1:
	print(1)
elif n % 2 == 0:
	print(2)
elif len(is_prime(n - 2)) == 1:
	print(2)
else:
	print(3)


import math
n = int(input())
if n <= 3:
	print(1)
if n > 3 and n % 2 == 0:
	print(2)
if n > 3 and n % 2 != 0:
	con1 = True
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			con1 = False
			break
	if con1:
		print(1)
	if not con1:
		n1 = n - 2
		con2 = True
		for i in range(2, int(math.sqrt(n1)) + 1):
			if n1 % i == 0:
				con2 = False
				break
		if con2:
			print(2)
		if not con2:
			print(3)


def isPrime(n):
	if (n == 2) | (n == 3):
		return True
	elif (n % 2 == 0) | (n % 3 == 0):
		return False
	else:
		nsq = int(n ** 0.5) + 1
		for k in range(3, nsq, 2):
			if n % k == 0:
				return False
		return True
n = int(input())
if isPrime(n):
	print(1)
elif isPrime(n - 2):
	print(2)
elif n % 2 == 0:
	print(2)
else:
	print(3)


def isPrime(n):
	p = 2
	while p * p <= n:
		if n % p == 0:
			return False
		p += 1
	return True
n = int(input())
if n == 2:
	print(1)
elif n == 3:
	print(1)
elif n == 4:
	print(2)
elif n == 5:
	print(1)
elif isPrime(n):
	print(1)
elif isPrime(n - 2):
	print(2)
elif n % 2 == 0:
	print(2)
else:
	print(3)


def rwh_primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]
primes = rwh_primes(44722)

def isPrime(z):
	if z < 44722:
		return z in primes
	else:
		for p in primes:
			if z % p == 0:
				return False
		return True
n = int(input())
if n & 1:
	if isPrime(n):
		print(1)
	elif isPrime(n - 2):
		print(2)
	else:
		print(3)
elif n == 2:
	print(1)
else:
	print(2)


def check(n):
	if n == 2:
		return 1
	elif n > 2:
		k = int(n ** 0.5) + 1
		b = 0
		for j in range(2, k + 1):
			if n % j == 0:
				return 0
			else:
				continue
		return 1
n = int(input())
if n == 2:
	print(1)
elif n % 2 == 0:
	print(2)
else:
	i = 0
	ans = 0
	while n > 2 and n - i >= 2:
		if check(n - i) == 1 and i != 1:
			n = i
			ans += 1
			i = 0
		else:
			i += 1
	print(min(ans + n // 2, 3))


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

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')
import time
start_time = time.time()
import collections

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def is_prime(n):
	for j in range(2, int(n ** 0.5) + 1):
		if n % j == 0:
			return False
	return True

def solve():
	N = getInt()
	if is_prime(N):
		return 1
	if N % 2 == 0:
		return 2
	if is_prime(N - 2):
		return 2
	return 3
print(solve())


import sys
x = int(input())
import math

def is_prime(n):
	if n % 2 == 0 and n > 2:
		return False
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		if n % i == 0:
			return False
	return True
if x == 2:
	print(1)
	return
if x == 4 or x == 6:
	print(2)
	return
if x % 2 == 0:
	print(2)
	return
elif is_prime(x):
	print(1)
	return
elif is_prime(x - 2):
	print(2)
	return
else:
	print(3)
	return


n = int(input())

def isprime(sn):
	for c in range(2, int(sn ** 0.5 + 1)):
		if sn % c == 0:
			return False
	return True
if isprime(n):
	print(1)
elif n & 1 == 0:
	print(2)
elif isprime(n - 2):
	print(2)
else:
	print(3)


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

def prime(n):
	q = floor(sqrt(n))
	prime = True
	for i in range(2, q + 1):
		if n % i == 0:
			prime = False
	return prime
if prime(n):
	print(1)
elif n % 2 == 0:
	print(2)
elif prime(n - 2):
	print(2)
else:
	print(3)


from math import *
from sys import *
from queue import *
from decimal import *

def pr(i):
	d = 2
	while d * d <= i:
		if i % d == 0:
			return 0
		d += 1
	return 1
n = int(input())
if n % 2 == 0 and n > 2:
	print(2)
elif pr(n):
	print(1)
elif pr(n - 2):
	print(2)
else:
	print(3)


import math

def tax(n):
	if n == 2:
		return 1
	if n % 2 == 0:
		return 2
	elif premier(n):
		return 1
	elif premier(n - 2):
		return 2
	else:
		return 3

def premier(k):
	if k < 2:
		return False
	else:
		for i in range(2, int(math.sqrt(k)) + 1):
			if k % i == 0:
				return False
		return True
print(tax(int(input())))


from math import floor, sqrt

def isprime(n):
	prime = True
	t = 2
	sqr = floor(sqrt(n))
	while t <= sqr and prime:
		prime = n % t != 0
		t += 1
	return prime
(n,) = map(int, input().split())
if isprime(n):
	print(1)
elif n % 2 == 0 or isprime(n - 2):
	print(2)
else:
	print(3)


from collections import Counter, defaultdict, deque
import heapq as hq
from itertools import count, islice
import math

def is_prime(n):
	return n > 1 and all((n % i for i in islice(count(2), int(math.sqrt(n) - 1))))
import sys
input = sys.stdin.readline
n = int(input())
if is_prime(n):
	print(1)
elif n % 2 == 0:
	print(2)
elif is_prime(n - 2):
	print(2)
else:
	print(3)


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

def max_p(n):
	if not is_prime(n):
		i = n - 2
		while i > 0:
			if is_prime(i):
				return i
			i -= 1
	else:
		return n
n = int(input())
if n == 2:
	ans = 1
elif n % 2 == 0:
	ans = 2
else:
	ans = 1
	while not is_prime(n):
		if n % 2:
			n = n - max_p(n)
			ans += 1
		else:
			ans += 1
			break
print(ans)


def is_izi(k):
	i = 2
	while i * i <= k:
		if k % i == 0:
			return 0
		i += 1
	return 1
n = int(input())
if is_izi(n):
	print(1)
elif n % 2 == 0:
	print(2)
elif n % 2 == 1:
	if is_izi(n - 2):
		print(2)
	else:
		print(3)


def test(n):
	maximum = int(n ** 0.5) + 3
	for i in range(2, min(maximum, n)):
		if n % i == 0:
			return False
	return True
n = int(input())
if n % 2 == 0:
	if n == 2:
		print(1)
	else:
		print(2)
elif test(n) == True:
	print(1)
elif test(n - 2) == True:
	print(2)
else:
	print(3)


import math

def isprime(n):
	if n == 2:
		return True
	sq = math.ceil(n ** 0.5) + 1
	for i in range(2, sq):
		if n % i == 0:
			return False
	return True

def solve(n):
	if isprime(n):
		return 1
	if n % 2 == 0:
		return 2
	if isprime(n - 2):
		return 2
	return 3
n = int(input())
print(solve(n))


mark = []
p = [1]
import math

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

def gen_prime(upto):
	for i in range(upto + 1):
		mark.append(True)
	for i in range(2, upto + 1):
		if mark[i]:
			p.append(i)
			for j in range(i, upto + 1, i):
				mark[j] = False
ans = 0

def cari_prima_terdekat(n):
	global ans
	if n > 0:
		for i in range(n, 0, -1):
			if isPrime(i):
				ans += 1
				print(i)
				cari_prima_terdekat(n - i)
				break
n = int(input())
if isPrime(n):
	print(1)
elif n % 2 == 0:
	print(2)
elif isPrime(n - 2):
	print(2)
else:
	print(3)


import sys
import collections
from collections import Counter
import itertools
import math
import timeit
input = sys.stdin.readline

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	divisors = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				divisors.append(i)
			else:
				divisors.extend([i, n // i])
	return divisors

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def flin(d, x, default=-1):
	left = right = -1
	for i in range(len(d)):
		if d[i] == x:
			if left == -1:
				left = i
			right = i
	if left == -1:
		return (default, default)
	else:
		return (left, right)

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 collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	return all((n % d for d in range(3, int(math.sqrt(n)) + 1, 2)))
n = ii()
if prime(n):
	print(1)
elif prime(n - 2) or not n % 2:
	print(2)
else:
	print(3)


def main():
	from math import sqrt
	n = int(input())
	if not n & 1:
		print(2 if n > 2 else 1)
		return
	for p in range(3, int(sqrt(n)) + 1, 2):
		if not n % p:
			break
	else:
		print(1)
		return
	n -= 2
	for p in range(3, int(sqrt(n)) + 1, 2):
		if not n % p:
			break
	else:
		print(2)
		return
	print(3)

def __starting_point():
	main()
__starting_point()


import os
import sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7

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 main():
	n = int(input())
	if isPrime(n):
		print(1)
	elif n % 2 == 0:
		print(2)
	elif isPrime(n - 2):
		print(2)
	else:
		print(3)

def nouse0():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse1():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse2():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
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 nouse3():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse4():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse5():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
main()


import math

def solve(n):
	if n < 2:
		return 0
	else:
		for i in range(2, int(math.sqrt(n) + 1)):
			if n % i == 0:
				return 0
	return 1
s = input().split()
n = int(s[0])
if solve(n) == 1:
	print(1)
elif n % 2 == 0:
	print(2)
elif solve(n - 2) == 1:
	print(2)
else:
	print(3)


import sys
input = sys.stdin.readline

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

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

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return 0
	return 1

def main():
	n = int(input())
	if isprime(n):
		print(1)
	elif n % 2:
		if isprime(n - 2):
			print(2)
		else:
			print(3)
	else:
		print(2)
	return
main()


I = lambda : int(input())
IL = lambda : list(map(int, input().split()))
S = [0] * 100001
S[0] = S[1] = 1
for i in range(2, 100001):
	if S[i]:
		continue
	else:
		for j in range(2 * i, 100001, i):
			S[j] = 1
primes = [i for (i, s) in enumerate(S) if not s]

def is_prime(x):
	for p in primes:
		if p * p > x:
			return True
		if x % p == 0:
			return False
n = I()
if is_prime(n):
	print(1)
elif n % 2 == 0 or is_prime(n - 2):
	print(2)
else:
	print(3)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nsmallest
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
from decimal import Decimal
mod = pow(10, 9) + 7
mod2 = 998244353

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

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

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

def l():
	return list(sp())

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

def sp():
	return map(int, data().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 prime(number):
	if number <= 1:
		return False
	if number == 2:
		return True
	if not number & 1:
		return False
	temp = 2
	while temp * temp <= number:
		if number % temp == 0:
			return False
		temp += 1
	return True
n = int(data())
if prime(n):
	out(1)
	exit()
if not n & 1:
	out(2)
	exit()
if prime(n - 2):
	out(2)
	exit()
out(3)


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()
if isprime(n):
	print(1)
elif n % 2 == 0:
	print(2)
elif isprime(n - 2):
	print(2)
else:
	print(3)


n = int(input())
if n == 2:
	print(1)
elif n % 2 == 0:
	print(2)
else:
	i = 2
	flag = True
	while i * i <= n:
		if n % i == 0:
			flag = False
			break
		i += 1
	if flag:
		print(1)
	else:
		i = 2
		flag = True
		while i * i <= n - 2:
			if (n - 2) % i == 0:
				flag = False
				break
			i += 1
		if flag:
			print(2)
		else:
			print(3)


from sys import stdin, stderr

def readInts():
	return map(int, stdin.readline().strip().split())

def print_err(*args, **kwargs):
	print(*args, file=stderr, **kwargs)

def isprime(n):
	prime = True
	if n < 4:
		return True
	for pt in range(2, n):
		if pt * pt > n:
			break
		if n % pt == 0:
			prime = False
			break
	return prime

def solve(n):
	if n < 4:
		return 1
	if n % 2 == 0:
		return 2
	prime = isprime(n)
	if isprime(n):
		return 1
	elif isprime(n - 2):
		return 2
	else:
		return 3
	return 0

def run():
	(n,) = readInts()
	print(solve(n))
run()


n = int(input())

def isPrime(x):
	s = [2, 3, 5, 7, 11]
	return x in s or all((pow(i, x, x) == i for i in s))
print(1 if isPrime(n) else (not isPrime(n - 2) and n % 2) + 2)


import math

def isprime(x):
	if x < 2:
		return 0
	for i in range(2, int(math.sqrt(x) + 1)):
		if x % i == 0:
			return 0
	return 1
a = int(input())
if isprime(a) == 1:
	print(1)
elif a % 2 == 0:
	print(2)
elif isprime(a - 2):
	print(2)
else:
	print(3)


x = int(input())
l = 0

def pr(x):
	if x == 2 or x == 3:
		return True
	elif x % 2 == 0 or x % 3 == 0 or x == 1:
		return False
	else:
		for n in range(3, int(x ** 0.5) + 2):
			if x % n == 0:
				return False
		return True
if pr(x):
	print(1)
elif x % 2 == 0:
	print(2)
elif pr(x - 2):
	print(2)
else:
	print(3)


def is_prime(x):
	for i in range(2, round(x ** 0.5) + 1):
		if x % i == 0:
			return False
	return True

def solve(n):
	if is_prime(n):
		print(1)
	elif n % 2 == 0 or (n > 4 and is_prime(n - 2)):
		print(2)
	else:
		print(3)
solve(int(input()))


n = int(input())
if n == 2 or n == 3:
	exit(print(1))
elif n % 2 == 0:
	exit(print(2))
for i in range(n, n - 3, -1):
	if i != n - 1:
		for j in range(2, int(i ** 0.5) + 2):
			if i % j == 0:
				break
			elif j == int(i ** 0.5) + 1:
				if i == n:
					exit(print(1))
				else:
					exit(print(2))
exit(print(3))


import math

def prime(n):
	if 1 < n <= 3:
		return True
	elif n <= 1 or n % 2 == 0:
		return False
	else:
		for i in range(3, math.isqrt(n) + 1, 2):
			if n % i == 0:
				return False
		else:
			return True
n = int(input())
if prime(n):
	print(1)
elif n % 2 == 0 or prime(n - 2):
	print(2)
else:
	print(3)


from math import *

def is_prime(a):
	if 2 == a:
		return True
	else:
		return all((a % i for i in range(2, ceil(sqrt(a) + 1))))
number = int(input())

def find_minimal_tax(number):
	if number == 2 or is_prime(number):
		return 1
	if number % 2 == 0 or is_prime(number - 2):
		return 2
	return 3
print(find_minimal_tax(number))


from math import sqrt

def is_prime(x):
	stop = int(sqrt(x)) + 1
	for i in range(2, stop):
		if x % i == 0:
			return False
	return True
n = int(input())
if is_prime(n):
	print(1)
elif n % 2 == 1:
	if is_prime(n - 2):
		print(2)
	else:
		print(3)
else:
	print(2)


import os, sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip('\r\n')

def isprime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			return False
	return True
n = int(input())
if isprime(n):
	print(1)
elif n % 2 == 0:
	print(2)
elif isprime(n - 2):
	print(2)
else:
	print(3)


import math

def isPrime(n):
	if n == 2:
		return True
	m = math.ceil(math.sqrt(n))
	for i in range(2, m + 1):
		if n % i == 0:
			return False
	return True

def sol():
	n = int(input())
	if isPrime(n):
		return 1
	if isPrime(n - 2):
		return 2
	if not n & 1:
		return 2
	return 3
print(sol())


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

def tax(n):
	if n == 2 or n == 5:
		return 1
	elif n % 2 == 0:
		return 2
	elif is_prime(n):
		return 1
	elif is_prime(n - 2):
		return 2
	else:
		return 3
n = int(input())
print(tax(n))


import sys, re, math
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from queue import Queue
from heapq import heappush, heappop, heapify, nlargest, nsmallest

def STR():
	return list(input())

def INT():
	return int(input())

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

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def sortListWithIndex(listOfTuples, idx):
	return sorted(listOfTuples, key=lambda x: x[idx])

def sortDictWithVal(passedDic):
	temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))[::-1]
	toret = {}
	for tup in temp:
		toret[tup[0]] = tup[1]
	return toret

def sortDictWithKey(passedDic):
	return dict(OrderedDict(sorted(passedDic.items())))
INF = float('inf')
mod = 10 ** 9 + 7

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
n = INT()
if n == 2 or n == 3 or n == 5:
	print(1)
elif n == 4:
	print(2)
elif n % 2 == 0:
	print(2)
elif isPrime(n):
	print(1)
elif isPrime(n - 2):
	print(2)
else:
	print(3)


def is_prime(n):
	j = 2
	while j * j <= n:
		if n % j == 0:
			return 0
		j += 1
	return 1
n = int(input())
if is_prime(n):
	print(1)
elif n % 2 == 0 or is_prime(n - 2):
	print(2)
else:
	print(3)


def sieve(n):
	mark = [i % 2 for i in range(n)]
	mark[1] = 0
	mark[2] = 1
	for value in range(3, n, 2):
		if mark[value] == 1:
			for i in range(value * 3, n, value * 2):
				mark[i] = 0
	return mark

def getPrimes(m):
	sieves = sieve(m)
	primes = [i for (i, f) in enumerate(sieves) if f]
	return (primes, sieves)

def isprime(n):
	if n == 2:
		return True
	if n == 3:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def find(n):
	for i in range(n, -1, -1):
		if isprime(i) and i != n - 1:
			return i

def main():
	n_init = int(input())
	n = n_init
	a = find(n)
	b = n - a
	result = 1
	while b != 0:
		n = b
		a = find(n)
		b = n - a
		result += 1
	if n_init % 2:
		if result > 3:
			result = 3
	elif n_init % 2 == 0:
		if result > 2:
			result = 2
	print(result)
main()


import math

def isPrime(n):
	a = math.sqrt(n)
	i = 2
	while i <= a:
		if n % i == 0:
			return False
		i += 1
	return True
n = int(input())
if isPrime(n):
	print(1)
elif n % 2 == 0:
	print(2)
elif isPrime(n - 2):
	print(2)
else:
	print(3)


from math import sqrt
limit = 2 * 1000000000
primes = [True for i in range(int(sqrt(limit)) + 1)]
tes = int(sqrt(sqrt(limit))) + 1
for i in range(2, tes):
	if primes[i]:
		for z in range(i * i, int(sqrt(2 * 1000000000)) + 1, i):
			primes[z] = False

def ptest(n):
	nonlocal primes
	for i in range(2, int(sqrt(n)) + 1):
		if primes[i]:
			if n % i == 0:
				return 0
	return 1
i = int(input().strip())
if i % 2 == 0:
	if i == 2:
		print(1)
	else:
		print(2)
elif ptest(i):
	print(1)
elif ptest(i - 2):
	print(2)
else:
	print(3)


def prime_factor(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return 0
		if i == 2:
			i += 1
		else:
			i += 2
	return 1
n = int(input())
if prime_factor(n):
	print('1')
elif n % 2 == 0 or prime_factor(n - 2):
	print('2')
else:
	print('3')


def isPrime(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())
if n == 2:
	print(1)
elif n % 2 == 0:
	print(2)
elif isPrime(n):
	print(1)
elif isPrime(n - 2):
	print(2)
else:
	print(3)