N = int(input())
is_prime = [1 for _ in range(N+1)]
is_prime[0] = 0; is_prime[1] = 0
for i in range(2, N+1):
    if not is_prime[i]: continue
    for j in range(i*2, N+1, i): is_prime[j] = 0

primes = [i for i in range(len(is_prime)) if is_prime[i]]
C = len(primes)

dp = [[-1] * (N+1) for _ in range(C+1)]
for i in range(C+1):
    dp[i][0] = 0
w = N
for i in range(C-1, -1, -1):
    for w in range(N+1):
        if w - primes[i] < 0: continue

        use = dp[i+1][w-primes[i]]
        dp[i][w] = max(
            use + 1,
            dp[i+1][w]
        )

print(dp[0][N] if dp[0][N] > 0 else -1)      


# DFS
# import sys
# sys.setrecursionlimit(1010101)

# dp = [[-1] * (N+1) for _ in range(C+1)]
# def dfs(i, w): # w を i~C-1番目の素数の和で表すことができる場合、その中での最大の和の回数を返す
#     if dp[i][w] > -1: 
#         return dp[i][w]
#     res = 0
#     if i == C or w < 0:
#         return -1
#     if w == 0:
#         return 0
    
#     res =  dfs(i+1, w)
#     use = -1
#     if w-primes[i] >= 0:
#         use = dfs(i+1, w-primes[i]) 
#     if use != -1:
#         res = max(res, use + 1)
#     dp[i][w] = res

#     return res


# print(dfs(0, N))