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
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
long long n,i,m,f1=1,f2=1,f,k;
int ile_cyfr=0,modulo=1, j;
int zli[1000006];
int kt[1000006];
string s;



int main(int argc, char *argv[])
{
	ios_base::sync_with_stdio(0);
	zli[1]=1;
	for(i=3;i<=1499998;++i) {f=(f1+f2)%100000000000000000;
							m = f%1000000;
							if(zli[m]==0) {
								kt[m] = i;
								zli[m] = 1;
								}			
							f2=f1;
							f1=f;}
	cin >> s;
	ile_cyfr = s.size();
	//k = 0;
	//for(i = 0; i < s.size();++i) k = k*10 + int(s[i]-'0');
	if(ile_cyfr > 6) {
					ile_cyfr = 6;	
					s = s.substr(s.size() - 7, 6);
					}
	//cout<<ile_cyfr<<endl;
	
	//for(i = 1; i <= ile_cyfr;++i) modulo *=10;
	for(i = 2; i < 1000000; ++i) {
		if(zli[i] == 1) {
			k = i;
			for(j = ile_cyfr - 1; k > 0 && j >= 0; --j){
				//cout << s[j];
				if(k%10 != int(s[j]-'0') ) break;
				k = k/10;
			}
			if(j == -1 ) {
				//cout << endl << i << endl;
				cout <<kt[i];
				break;
				}
			}
		}
	
	if(i==1000000) cout <<"NIE";
		
	

 
    return 0;
}