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
125
#include <iostream>
#include <string>
#include <sstream>

using namespace std;
string fib[10000];
int P[1000];
int KMP (string a, string b)
{
	string last='#'+a+'#'+b;
	int t=P[0];
	for (int i=2; i <=last.size(); i++)
	{
		while (t>0 && last[t+1]!=last[i])
		t=P[t];
		if(last[t+1]==last[i])
		t++;
		P[i]=t;
		}
	}

int main() {
    
     fib[0]='0';
    fib[1]='1';
    for (int k=2; k <=1000; k++)
    {
    string m, w;
    m=fib[k-2];
    w=fib[k-1];
    stringstream s;
    stringstream suma;
    
    for( int i = m.size() - 1; i >= 0; i-- )
         s << m[ i ];
    
   m = s.str();
    s.str( "" );
    
    for( int i = w.size() - 1; i >= 0; i-- )
         s << w[ i ];
    
    w = s.str();
    
    int x, zap = 0;
    
    for( int i = 0; i < w.size(); i++ ) {
        
        if( m.size() > i && w.size() > i ) 
		{
            x=( char ) m[i] - 48 +(char) w[i] - 48;
        }
        else {
            x=( (char) w[i] - 48 );
        }
        
       x += zap;
        
        if( x > 9 )
		 {
           zap = 1;
            suma << x % 10;
        }
        else 
		{
            suma << x;
            zap = 0;
        }
    }
    
    if( zap) { suma << zap; }
    
    string wynik = suma.str();
    string g;
    for( int i = wynik.size() - 1; i >= 0; i-- )
	{
		g.push_back(wynik[i]);
      }
     
    fib[k]=g;
}



// KMP
//cout << fib[10];
string st;
cin >>st;
int sw=0;
int i=0;

while (st[i]=='0' && i< st.size())
{
 	sw++;
 	i++;
}


string t;

 for( int i =sw; i<st.size(); i++ )
	{
		t.push_back(st[i]);
      }
     //cout << t <<endl;

for (int i=0; i <10000; i++)
{
	
	KMP(t,fib[i]);
	if(P[t.size()+fib[i].size()+1]==t.size())
	{
		cout << i;
		return 0;
	}
	
	for(int j=0; j <1000; j ++)
	{
		P[j]=0;
	}
}
cout << "NIE";

    return 0;
}