from math import sqrt
from tqdm import tqdm
N = int(input())

def is_prime(n, primes):
	for prime in primes:
		if n/prime == n//prime:
			return False
	else:
		return True

primes = [2]
sum_primes = [2]
_sum = 2
for i in range(3, N+1, 2):
	if is_prime(i, primes):
		primes.append(i)
		_sum += i
		sum_primes.append(_sum)

hash_keys = [list() for _ in range(60403)]

def hash_func(n):
	return n%60403


data = dict()
keys = list()
_len = len(primes)
count = 1
for prime, _sum in zip(primes[::-1], sum_primes[::-1]):
	# print('prime: {}, _sum: {}'.format(prime, _sum))
	# print(data)
	if prime not in hash_keys[hash_func(prime)]:
		data[prime] = 1
		hash_keys[hash_func(prime)].append(prime)
	for key in keys:
		if key+prime > N: continue
		if key+_sum < N: continue
		if key+prime not in hash_keys[hash_func(key+prime)]:
			data[key+prime] = data[key] + 1
			hash_keys[hash_func(key+prime)].append(key+prime)
		else:
			data[key+prime] = max(data[key+prime], data[key]+1)
	keys = list(data.keys()).copy()
	count += 1
# for key in data.keys():
# 	print('{} {}'.format(key, data[key]))


if N in data.keys():
	print(data[N])
else:
	print(-1)