from math import inf


def main():
    n = int(input())
    dp = [inf] * (n + 1)
    dp[1] = 0
    for i in range(1, n + 1):
        for k in range(1, n // i + 1):
            dp[i * k] = min(dp[i] + k, dp[i * k])
    print(dp[n])


if __name__ == "__main__":
    main()