import sys
import math

def sieve(n):
    if n < 2:
        return []
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(math.isqrt(n)) + 1):
        if sieve[i]:
            sieve[i*i : n+1 : i] = [False] * len(sieve[i*i : n+1 : i])
    primes = [i for i, is_prime in enumerate(sieve) if is_prime]
    return primes

n = int(sys.stdin.readline())

primes = sieve(n)

if not primes:
    print(-1)
    sys.exit()

sum_primes = []
s = 0
for p in primes:
    s += p
    sum_primes.append(s)
    if s > n:
        break

max_m = 0
for i in range(len(sum_primes)):
    if sum_primes[i] <= n:
        max_m = i + 1
    else:
        break

for m in range(max_m, 0, -1):
    sum_s = sum_primes[m-1]
    if sum_s > n:
        continue
    D = n - sum_s
    if D == 0:
        print(m)
        sys.exit()
    if (sum_s % 2) != (n % 2):
        continue
    if D % 2 != 0:
        continue
    primes_in_m = primes[:m]
    primes_set = set(primes_in_m)
    for p in primes_in_m[1:]:  # Exclude the first prime (2)
        q = p + D
        if q in primes_set:
            continue
        if q in primes:
            print(m)
            sys.exit()

print(-1)