N=int(input())

inf=float("inf")
DP=[inf]*(N+1); DP[1]=0

for i in range(1,N+1):
    k=2
    while k*i<=N:
        DP[k*i]=min(DP[k*i],DP[i]+k)
        k+=1

print(DP[N])