1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
using namespace std;
#define inf 1000000005
typedef long long ll;
typedef double db;
void gn(int &x){
    int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')sg=-1,x=0;else x=c-'0';
    while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';
    x*=sg;
}
void gn(ll &x){
    int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')sg=-1,x=0;else x=c-'0';
    while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';
    x*=sg;
}
ll mo;
int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}

ll mul(ll a,ll b){a>=mo?a%=mo:0;b>=mo?b%=mo:0;ll ans=0;do{if(b&1)(ans+=a)>=mo?ans-=mo:0;(a+=a)>=mo?a-=mo:0;}while(b>>=1);return ans;}
struct mat{ll a,b,c,d;};
mat operator*(const mat&x,const mat&y){
	return (mat){(mul(x.a,y.a)+mul(x.b,y.c))%mo,(mul(x.a,y.b)+mul(x.b,y.d))%mo,
				(mul(x.c,y.a)+mul(x.d,y.c))%mo,(mul(x.c,y.b)+mul(x.d,y.d))%mo};
}
mat po(mat x,ll p){
	mat ans=(mat){1,0,0,1};
	do{
		if(p&1)ans=ans*x;
		x=x*x;
	}while(p>>=1);
	return ans;
}

ll fib(ll n){
	mat x=(mat){1,1,1,0};
	x=po(x,n);
	return x.c;
}

ll f[1000000];
int n;
ll r;
ll m2,m5;
ll r2[1000000],r5[100];
int r2tot=0,r5tot=0;
int r2ok[1000000]={0};


void test(ll x){
	mo=1;
	for (int i=1;i<=n;i++)mo*=10;
	ll y=fib(x);
	if(r==y)printf("yes\n");
	else printf("no\n");
}
int work(ll x){
	ll cur=x;
	for (int i=0;i<m2;i++){
		if(r2ok[cur%m2]){
			while(cur<1000)cur+=m2*m5;
			cout<<cur<<endl;
			//test(cur);
			return 1;
		}
		cur+=m5;
	}
	return 0;
}
int main()
{
	char s[20];
	scanf("%s",s+1);
	n=strlen(s+1);
	r=0;
	for (int i=1;i<=n;i++)r=r*10+s[i]-'0';


	mo=1;
	for (int i=1;i<=n;i++)mo*=2;
	f[0]=0;f[1]=1;
	for (int i=2;;i++){
		f[i]=(f[i-1]+f[i-2])%mo;
		if(f[i-1]==0 && f[i]==1){
			m2=i-1;
			break;
		}
	}
	ll d2=r%mo;
	for (int ii=0;ii<m2;ii++)if(f[ii]==d2){
		r2[++r2tot]=ii;
		r2ok[ii]=1;
	}
	if(r2tot){
		for (int i=2;i<20;i++){
			f[i]=(f[i-1]+f[i-2])%5;
		}
		for (int j=0;j<20;j++)if(f[j]==r%5){
			ll xx=j;
			m5=20;mo=5;
			for (int i=2;i<=n;i++){
				mo*=5;ll d5=r%mo;
				while(fib(xx)!=d5)xx+=m5;
				m5*=5;
			}
			r5[++r5tot]=xx;
		}
		for (int i=1;i<=r5tot;i++)if(work(r5[i]))return 0;
		printf("NIE\n");
	}else printf("NIE\n");
	return 0;
}