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
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
const ll ten = 100 * 1000;
ll mod;
// 4 6 10 12 14 18 20 22 26 28 30

ll mul(ull a, ull b) {
	ull s = 0;
	while(b) {
		s = (s + b % 10 * a) % mod;
		b /= 10;
		a = a * 10 % mod;
	}
	return s;
}

ll f[ten * 3 / 2];
unordered_map<ll,ll> m;
ll fibo(ll i) {
	if(i < ten * 3 / 2) return f[i];
	if(m.count(i)) return m[i];
	ll x = fibo(i / 2);
	ll y = fibo(i / 2 + 1);
	if(i % 2) return m[i] = (mul(x, x) + mul(y, y)) % mod;
	return m[i] = mul(x, (2 * y - x + mod) % mod); 
}

void finish(ll i) {
	printf("%lld\n", i);
	exit(0);
}

void maybe(ll i, ll nowTen, ll n, ll mod) {
	if(nowTen == mod) {
		if(fibo(i) == n && i > 1000) finish(i);
		return;
	}
	for(int dig = 0; dig <= 9; ++dig)
		if(fibo(i + dig * nowTen * 3 / 2) % (nowTen * 10) == n % (nowTen * 10))
			maybe(i + dig * nowTen * 3 / 2, nowTen * 10, n, mod);
}

int main() {
	char sl[20];
	scanf("%s", sl);
	int d = strlen(sl);
	ll n = 0;
	mod = 1;
	for(int i = 0; i < d; ++i) {
		n = 10 * n + sl[i] - '0';
		mod *= 10;
	}
	f[0] = 0;
	f[1] = 1;
	bool overflow = false;
	vector<ll> w, singles;
	for(int i = 0; i < ten * 3 / 2; ++i) {
		if(i >= 2) f[i] = f[i-2] + f[i-1];
		if(f[i] >= mod) {
			f[i] -= mod;
			overflow = true;
		}
		if(f[i] == n && (d == 1 || sl[0] != '0' || overflow))
			finish(i);
		else if(f[i] == n) singles.pb(i);
		if(f[i] % ten == n % ten) w.pb(i);
	}
	for(ll i : singles) for(int j = 1; j <= 10; ++j) {
		ll x = i + j * ten * 3 / 2;
		if(fibo(x) == n) finish(x);
	}
	for(ll i : w) maybe(i, ten, n, mod);
	puts("NIE");
	return 0;
}