n = int(input())
if n == 1:
    print(1)
    exit()
x = [0,1,1]
for i in range(3,10000):
    x.append(x[-2]+x[-1])
    x[-1] %= n
    if x[-1] == 0:
        print(i)
        break