N = int(input())

prime = [True] * (N + 1)
P = []
for i in range(2, N+1):
    if prime[i]:
        P.append(i)
        for j in range(i+i, N+1, i):
            prime[j] = False

n = len(P)

dp = [[-1 for _ in range(N + 1)] for _ in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    p = P[i]

    for j in range(N + 1):
        if dp[i][j] == -1 : continue

        if dp[i + 1][j] == -1 : dp[i + 1][j] = dp[i][j]
        else : dp[i + 1][j] = max(dp[i+1][j], dp[i][j])

        if j + p > N : continue
        if dp[i + 1][j + p] == -1 : dp[i + 1][j + p] = dp[i][j] + 1
        else : dp[i + 1][j + p] = max(dp[i+1][j + p], dp[i][j] + 1)


print(dp[n][N])