n = int(input())

s = [0] * 20001

cn = [False] * 20001

s[2] = 1

for i in range(3, n + 1, 2):
    if cn[i]:
        continue
    else:
        for j in range(i * 3, n + 1, i * 2):
            cn[j] = True
        for k in range(n - i, 1, -1):
            if s[k] == 0:
                continue
            elif s[k] + 1 > s[k + i]:
                s[k + i] = s[k] + 1
        s[i] = max(1, s[i])

if s[n] == 0:
    print(-1)
else:
    print(s[n])