def max_prime_partition(N):
    from functools import lru_cache

    # エラトステネスの篩で素数列挙
    def sieve(limit):
        is_prime = [True] * (limit + 1)
        is_prime[0] = is_prime[1] = False
        primes = []
        for i in range(2, limit + 1):
            if is_prime[i]:
                primes.append(i)
                for j in range(i * i, limit + 1, i):
                    is_prime[j] = False
        return primes

    primes = sieve(N)
    P = len(primes)
    import sys
    sys.setrecursionlimit(10101010)
    # メモ化再帰 DFS (残りの値 `remain` を `i` 以降の素数で作る)
    @lru_cache(None)
    def dfs(remain, i):
        if remain == 0:
            return 0  # 何も足さないときのカウントは0
        if remain < 0 or i >= P:
            return -float("inf")  # 不可能な場合

        # 使わない場合
        res = dfs(remain, i + 1)

        # 使う場合（異なる素数のみ）
        if primes[i] <= remain:
            res = max(res, 1 + dfs(remain - primes[i], i + 1))

        return res

    ans = dfs(N, 0)
    return ans if ans > 0 else -1

# テストケース
N = int(input())
print(max_prime_partition(N))