def get_primes(size=10**7):
    is_prime = [True] * (size + 1)
    is_prime[0] = is_prime[1] = False
    primes = []
    for i in range(size + 1):
        if not is_prime[i]:
            continue
        primes.append(i)
        j = 2
        while i * j <= size:
            is_prime[i * j] = False
            j += 1
    return primes


N = int(input())
primes = get_primes(N)
dp = [-1] * (N + 1)
dp[0] = 0
for p in primes:
    for i in range(N, p - 1, -1):
        if dp[i - p] == -1:
            continue
        dp[i] = max(dp[i - p] + 1, dp[i])
print(dp[N])