#include<stdio.h>

int main()
{
    int m,ans=0;
    scanf("%d",&m);
    int fib[100001];
    fib[0]=0;
    fib[1]=1;
    for(int i=2;i<100001;i++)
    {
        fib[i]=(fib[i-1]+fib[i-2])%m;
        if((fib[i-1])%m==0&&(fib[i])%m==1)
        {
            ans=i-1;
            break;
        }
    }
    printf("%d",ans);
}