def chmax(DP,i,v):
    if DP[i] < v: DP[i] = v

N = int(input())
distinct_prime_factor_count = [0]*(N+1)
primes = []
for i in range(2, N+1):
    if distinct_prime_factor_count[i] == 0:
        primes.append(i)
        for num in range(i, N+1, i):
            distinct_prime_factor_count[num] += 1

L = len(primes)
dp = [[-1] * (N + 1) for _ in range(L + 1)]
dp[0][0] = 0

for i in range(L):
    p = primes[i]
    for j in range(0, N + 1):
        if dp[i][j] == -1:
            continue
        chmax(dp[i + 1], j, dp[i][j])
        if j + p <= N:
            chmax(dp[i + 1], j + p, dp[i][j] + 1)

print(dp[-1][-1])