def Eratosthenes(maxNum):
    sieve = list(range(2,maxNum+1))
    result = []
    while sieve:
        prime = sieve[0]
        sieve = [x for x in sieve if x % prime]
        result.append(prime)
    return result
 
N=int(input())
primes = Eratosthenes(N)
pLen = len(primes)

tree = [2] + [0]*(pLen-1)    # binary tree, 2 is first prime
depth = 1    # searching depth
s = 2    # sum of adding elements
result = -1
elements = 1    # numbers of prime numbers now searching



while depth:
    # required at least (result - elements) + 1 elements if update results 
    if depth < pLen and s + sum(primes[depth:depth+max(0,result-elements)+1])  <= N:
        tree[depth] = primes[depth]
        s = s + primes[depth]
        depth = depth + 1
        elements = elements + 1
    else:
        # return to last added element and pop it.
        depth = depth - 1
        while depth:
            if tree[depth]:
                tree[depth] = 0
                s = s - primes[depth]
                depth = depth + 1
                elements = elements - 1
                break
            else:
                depth = depth -1
    if s == N and elements > result:
        result = elements

print(result)