#include <stdio.h>

	
int f[10000002];
int main()
{
    int m,n;
    scanf("%d",&m);
    f[0]=0;
    f[1]=1;
    f[2]=1;
    for (n = 3; n <= m*m; n++)
    {
        f[n]=(f[n-1]+f[n-2]) % m;
        if(f[n] ==1 && f[n-1] ==0) break;
    }
    printf("%d",n-1);
    return 0;
}