N=int(input())
F=[0,1]
i,j,k=0,1,1
while 1:
	F[j]=(F[j]+F[i])%N
	if F[j]<1:print(k),exit()
	i,j,k=j,i,k+1