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: interview

Starter code:

Solutions:
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 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)
else:
  if n == 2:
    print(1)
  else:  
    print(2)


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)

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


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)

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


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)
else:
    if test(n) == True:
        print(1)
    elif test(n - 2) == True:
        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()


def prime(x):
    p=int(n**.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)


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

# from math import ceil,floor
# def matches(n,left):
# 	pass
# n = int(input())
# if n%2 == 0:
# 	print(1+matches(n//2,0))
# else:
# 	print(1+matches(ceil(n/2),1))	
# print(ans)	
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))		


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

import math


# get line input split by space
def getLnInput():
    return input().split()


# ceil(a / b) for a > b
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)
    else:
        if isPrime(n - 2):
            print(2)
        else:
            print(3)
    return


main()


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


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

def prime(x):
	i = 2
	while i * i <= x:
		if x % i == 0:
			return False
		i += 1
	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
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

else:
    if (is_prime(x)):
        print(1)
        return
    else:
        if (is_prime(x -2)):
            print(2)
            return
        else:
            print(3)
            return


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


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
    else:
        if isPrime(n-2):
            ans = 2
        else:
            ans = 3
stdout.write(str(ans))


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):
        #print(max_p(n))
        if n % 2:
            n = n - max_p(n)
            #print(n)
            ans += 1
        else:
            ans += 1
            break

print(ans)

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)
else:
    if 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))

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)