n =int(input())
prime = []
num = [i for i in range(2, n+1)]
while num[0]**2 <= n:
    p = num[0]
    prime.append(p)
    num = [i for i in num if i%p!=0]
prime += num
m = [-1]*(n+1)
m[0] = 0
for i in range(n+1):
    if m[i] == -1:
        continue
    for p in prime:
        if i+p <= n:
            m[i+p] = max(m[i+p], m[i]+1)

print(m[n])