N = int(input()) INF = 1 << 30 def list_primes(limit): primes = [] is_prime = [True] * (limit + 1) is_prime[0] = False is_prime[1] = False for p in range (0, limit + 1): if not is_prime[p]: continue primes.append(p) for i in range(p*p, limit + 1, p): is_prime[i] = False return primes primes = list_primes(N) dp = [-INF] * (N+1) dp[0] = 0 for p in primes: for i in range(N+1)[::-1]: if i - p < 0: break dp[i] = max(dp[i], dp[i-p] + 1) print(dp[-1] if dp[-1] > 0 else -1)