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
/*	Arkadiusz Wróbel
 *
 *	Konkurs: Potyczki Algorytmiczne 2015, runda 2A
 *	Zadanie: Fibonacci
 */
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define REP(I, N) for(int I=0; I<(N); ++I)
#define FOR(I, M, N) for(int I=(M); I<=(N); ++I)
#define FORD(I, M, N) for(int I=(M); I>=(N); --I)
#define FOREACH(IT, CON) for(__typeof(CON.begin()) IT=CON.begin(); IT!=CON.end(); ++IT)
#define ST first
#define ND second
#define MP make_pair
#define PB push_back
#define SIZE(CON) ((int)CON.size())
const int INF=1000000000;
const LL INFLL=1000000000000000000LL;

LL M;
LL X;

int main()
{
	char s[32];
	scanf("%s", s);
	M = 1;
	X = 0;
	for (int i = 0; s[i]; ++i) {
		M *= 10;
		X *= 10;
		X += s[i] - '0';
	}
	
	LL f1 = 0, f2 = 1;
	
	LL C = max(10000LL, M / 10 * 15 + 1000);
	for (LL i = 2; i < C; ++i) {
		LL f = (f1 + f2) % M;
		f1 = f2;
		f2 = f;
		if (i >= 100 && f == X) {
			// >= 100, żeby liczba nie była zbyt krótka
			// Jeśli przez to pominiemy wynik, to na szczęście sprawdzamy dodatkowy 1000 liczb.
			printf("%lld\n", i);
			return 0;
		}
	}
	
	printf("NIE\n");
	
	return 0;
}