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
//Jan Omeljaniuk
//
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <bitset>
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <sstream>
#define unm unsigned long long int
#define nm long long int
#define uint unsigned int

using namespace std;

inline unm period(unm x) {
	if(x==10)
		return 60;
	if(x==100)
		return 300;
	return 15 * x/10;
}

bool exists(unm x) {
	//cerr << "Exists(" << x << ")\n ";
	if( x >= 100ULL && ( (x-100ULL)%8ULL == 0ULL || (x-100ULL)%8ULL == 2ULL ) )
		return false;
	if( x >= 1002ULL &&  (x-1002ULL)%16ULL == 0ULL )
		return false;
	if( x >= 10002ULL && (x-10002ULL)%32ULL == 0ULL )
		return false;
	return true;
}

string n;

unm test(string v){

	unm sz = v.size();
	unm modulo = 1;
	unm n = atoll(v.c_str());

	while(sz--)
		modulo*=10;

	//cerr << modulo << "\n";
	//cerr << period(modulo);
	unm last=1, prelast=0,temp;
	bool f = false;
	for(unm i=2;i<=period(modulo)+1;++i){
		temp = (last+prelast)%modulo;
		if(temp>=modulo/10)
			f=true;
		//temp = last+prelast;
		prelast = last;
		last = temp;
		//if(i==1525)
		//cerr << i << ". " << temp <<"\n";
		//if(temp == x){
		if(f&&temp == n){
			//cerr << temp << "\n";
			return i;
		}
	}

	return 0;

}


int main(){

   ios_base::sync_with_stdio(false);

   cin >> n;

	if(n[0]=='0'||exists(atoll(n.c_str()))){
		nm temp = test(n);
		if(temp == 0){
			cout << "NIE\n";
			return 0;
		}
		cout << temp << "\n";
	} else {
		cout << "NIE\n";
	}

	return 0;
}