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
#include<bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;
vector< pair<int,int> >fib;
void prep(){
    vector<pair<int,int> >v; 
    int mod=1e3;
    int a=0,b=1;
    v.push_back(mp(0,0)); v.push_back(mp(1,1));
    for(int i=2;i<3*mod/2;i++){ 
	int c=(a+b)%mod;
	a=b;
	b=c;
	v.push_back(mp(c,i));
    }
    sort(v.begin(),v.end());
    
    fib.push_back(make_pair(0,0));
    for(int i=0;i<v.size();i++)
	if(fib.back().f!=v[i].f)
	    fib.push_back(v[i]);
    
    //for(int i=0;i<fib.size();i++)
	//printf("%d %d\n",fib[i].f,fib[i].s);
}
unsigned long long mod;
unsigned long long mnoz(unsigned long long a,unsigned long long n){
    if(n==0)return 0;
    unsigned long long l=mnoz(a,n/2);
    if(n%2==1)return (a+l+l)%mod;
    return (l+l)%mod;
}
void wypisz(vector< vector<unsigned long long> >&v){
    printf("%lld %lld\n%lld %lld\n\n",v[0][0],v[0][1],v[1][0],v[1][1]);
}
void mno(vector< vector<unsigned long long> > &a,vector< vector<unsigned long long> > &b){
    vector< vector<unsigned long long> >c; c.resize(2); c[0].resize(2); c[1].resize(2);
    c[0][0]=(mnoz(a[0][0],b[0][0])+mnoz(a[0][1],b[1][0]))%mod;
    c[0][1]=(mnoz(a[0][0],b[0][1])+mnoz(a[0][1],b[1][1]))%mod;
    c[1][0]=(mnoz(a[1][0],b[0][0])+mnoz(a[1][1],b[1][0]))%mod;
    c[1][1]=(mnoz(a[1][0],b[0][1])+mnoz(a[1][1],b[1][1]))%mod;
    
    a=c;
}
unsigned long long Fib(unsigned long long n){
   vector< vector<unsigned long long> >a; a.resize(2); a[0].resize(2); a[1].resize(2);
   a[0][0]=1; a[0][1]=1;
   a[1][0]=1; a[1][1]=0;
   
   vector< vector<unsigned long long> >v; v.resize(2); v[0].resize(2); v[1].resize(2);
   v[0][0]=1; v[0][1]=0;
   v[1][0]=0; v[1][1]=1;
   while(n)
   {
      if(n%2 == 1) mno(v,a);
      mno(a,a);
      n /= 2;
   }
   return v[0][1];
}
int N;
unsigned long long X=0;
void wczytaj(){
    string s;
    cin>>s;
    N=s.size();
    for(int i=0;i<N;i++)
	X=X*10+s[i]-'0';
    
}
void naPale(){
    for(int i=0;i<fib.size();i++)
	if(fib[i].f==X){
	    printf("%d",fib[i].s);
	    return;
	}
}
unsigned long long odp;
void naJarka(){
    mod=1000;
    for(int i=0;i<fib.size();i++)
	if(fib[i].f==X%mod){
	    odp=fib[i].s;
	    break;
	}
    mod*=10;
    for(int i=4;i<=N;i++){
	bool good=false;
	for(int j=0;j<=15;j++){
	    //printf("%lld\n",Fib(odp+3*mod/20*j));
	    if(Fib(odp+3*mod/20*j)==X%mod){
		//printf("odp %lld\n",odp);
		odp+=3*mod/20*j;
		good=true;
	    }
	}
	if(!good){
	    printf("NIE");
	    return;
	}
	//printf("odp %lld\n",odp);
	mod*=10;
    }
    printf("%lld\n",odp);
}
int main(){
    wczytaj();
    if((X-4)%8==0 || (X-6)%8==0){
	printf("NIE");
	return 0;
    }
    prep();
    
    if(N<4)
	naPale();
    else
	naJarka();
    
    //printf("fib %lld",Fib(odp));
    return 0;
}