N = int(input())
pa = [i for i in range(5, N+1, 2) if i % 3]
pr = [2, 3]
rN = int(N**0.5)
while True:
    m = pa[0]
    if m > rN:
        break
    pr += [m]
    pa = [n for n in pa[1:] if n % m]
pr += pa
pa = [1]+[0]*N
for r in pr:
    for j in range(N,-1,-1):
        if pa[j]>0 and j+r<=N:
            pa[j+r]=max(pa[j+r],pa[j]+1)
print(pa[N]-1)