import numpy as np

N = int(input())

prime = []
for i in range(2,N+1):
    for j in prime:
        if i%j==0:break
    else:
        prime.append(i)

dp = np.zeros((len(prime)+1,N+1),int)
dp[0,0]=1

for i in range(len(prime)):
    for j in range(1,N+1):
        if j-prime[i]>=0:
            tmp = dp[:i+1,j-prime[i]].max()
            if tmp!=0:
                dp[i+1,j] = tmp+1
            else:
                dp[i+1,j] = 0
        else:
            dp[i+1,j] = 0
dp -= 1
print(dp[:,N].max())