# Arup Guha
# 10/18/2022
# A Second More Efficient Solution to CIS 3362 Hmk #5, Question #7

''' Output for n = 20 is:
    The answer here is 281929.
    If the one isn't counted, the min value for 20 steps is 557057.

    This runs in about 25% the time that version 2 runs.
'''

# Regular GCD function.
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a%b)

# Returns the smallest Prime Factor of n.
def smallestPFactor(n):
    i = 2
    while i*i <= n:
        if n%i == 0:
            return i

        i += 1
    return n

# Solves the problem for the input value.
def main():

    # Get user input.
    steps = int(input("What value of f(n) are you looking for?\n"))

    # phi[i] will store phi(i).
    phi = [0,1,1]
    
    # dp[i] will store f(i). I seed the array here.
    dp = [0,1,2]

    # Next value we are solving for.
    i = 3
    
    # Break out when we find the value.
    while True:

        # Figure out phi of this value. Then, use our look up of f(phi(n))
        # To figure out what f(n) should be.

        primeDiv = smallestPFactor(i)
        if primeDiv == i:
            phi.append(i-1)
        else:

            # Divide out each copy of primeDiv.
            tmp = i
            term = 1
            while tmp%primeDiv == 0:
                tmp //= primeDiv
                term *= primeDiv

            # Use Phi Formula separated out by prime factors here.
            phi.append(phi[tmp]*(term - term//primeDiv))            
        
        # Here is what we want.
        dp.append(dp[phi[-1]]+1)

        # We got where we needed to, let's break out.
        if dp[phi[-1]]+1 == steps:
            print("min value for",steps,"steps is",len(dp)-1)
            break

        # Go to next.
        i+= 1

# Run it!
main()