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
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

const ll INF = 1000000000000000000LL;
const ll MAX_LL = 9000000000000000000LL;

ll multiply(ll a, ll b) {
	ll ret = 0;
	while (a > 0) {
		if (a%2 == 1) {
			ret = (ret + b) % INF;
		}
		a /= 2;
		b = (b + b) % INF;
	}
	return ret;
}

struct matrix {
	ll t[2][2];
	matrix() { t[0][0] = t[0][1] = t[1][0] = t[1][1] = 0; }
	matrix(ll _t00, ll _t01, ll _t10, ll _t11) { t[0][0] = _t00, t[0][1] = _t01, t[1][0] = _t10, t[1][1] = _t11; }
	matrix operator * (matrix b) {
		matrix ret;
		for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) {
			ret.t[i][j] = (ret.t[i][j] + multiply(t[i][k], b.t[k][j])) % INF;
		}
		return ret;
	}
};

matrix spb(matrix a, ll x) {
	if (x == 1) return a;
	if (x%2 == 1) return spb(a, x-1) * a;
	matrix ret = spb(a, x/2);
	return ret * ret;
}

ll fib(ll i) {
	if (i == 0) return -1;
	if (i == 1) return 1;
	return spb(matrix(1, 1, 1, 0), i-1).t[0][0];
}

bool seems_ok(ll n) {
	if (n%2 == 1) return false;
	//if (n == 2) return true;
	for (ll i = 8; i <= max(16LL, n+n); i = i+i) {
		if (n%i == 2 || n%i == 4 || n%i == 6) return false;
	}
	return true;
}

ll n;

ll solve(ll n, ll mod) {
	ll pow10 = 1, mult = 1, ret = 0;
	while (pow10 < mod) {
		//printf("ret = %lld\n", ret);
		if (pow10 == 1) mult = 1;
		//else mult = 6 * pow10;
		else if (pow10 == 10) mult = 60;
		else if (pow10 == 100) mult = 300;
		else mult = (pow10/10LL) * 15LL;
		for (ll i = 1; i < 400 && (i*mult < MAX_LL); i++) {
			ll candidate = (n - fib(i * mult + ret) + INF) % mod;
			if ((fib(i * mult + ret) % (10LL * pow10) == n % (10LL * pow10)) && seems_ok(candidate/(pow10*10LL))) {
				//printf("%lld\n", candidate/(pow10*10LL));
				ret += i * mult;
				break;
			}
		}
		pow10 = pow10 * 10LL;
	}
	ll kochamjulie = ret;
	if (fib(ret)%mod == n) printf("%lld\n", kochamjulie); 
	else printf("NIE\n");
}

int main() {
	char in[25];
	scanf("%s", in);
	int l = strlen(in);
	ll pot10 = 1, n = 0;
	for (int i = l-1; i >= 0; i--) {
		n = n + ll(in[i]-'0') * pot10;
		pot10 = pot10 * 10LL;
	}
	ll mod = pot10;
	solve(n, mod);
	
	return 0;
}