N=int(input())
F=[0,1%N]
for i in range(2,10000):
    F.append((F[-1]+F[-2])%N)
F[0]=None
ans=F.index(0)
print(ans)