def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    primes = [i for i, prime in enumerate(is_prime) if prime]
    return primes, is_prime

def main():
    N = int(input().strip())
    if N < 2:
        print(-1)
        return
    
    # Generate primes up to a large enough value (2*1e4)
    primes_list, is_prime = sieve(20000)
    
    sum_primes = []
    primes_used = []
    current_sum = 0
    for p in primes_list:
        if current_sum + p > N:
            break
        current_sum += p
        sum_primes.append(current_sum)
        primes_used.append(p)
    
    # Check for all possible k from maximum possible down to 1
    for k in range(len(sum_primes), 0, -1):
        sum_k = sum_primes[k-1]
        if sum_k == N:
            print(k)
            return
        d = N - sum_k
        
        # Check condition a: d is a prime and larger than last prime in current sum
        if d > primes_used[k-1] and is_prime[d]:
            print(k + 1)
            return
        
        # Check condition b: find if there is a prime[i] such that prime[i] + d is a prime larger than current last prime
        max_prime_in_k = primes_used[k-1]
        for i in range(k):
            q = primes_used[i] + d
            if q > max_prime_in_k and is_prime[q]:
                print(k)
                return
    
    # Check if N itself is a prime (when k=1 is possible)
    if is_prime[N]:
        print(1)
        return
    
    print(-1)

if __name__ == "__main__":
    main()