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
import java.util.Scanner;

public class fib {

	public static void main(String[] args) {
		
		
		long fc[][] = {
				{0, 1, 2},
				{5, 8, 7},
				{55, 89, 12},
				{610, 987, 17},
				{4181, 6765, 21},
				{46368, 75025, 26},
				{514229, 832040, 31},
				{5702887, 9227465, 36},
				{39088169, 63245986, 40},
				{433494437, 701408733, 45},
				{4807526976L, 7778742049L, 50},
				{53316291173L, 86267571272L, 55},
				{591286729879L, 956722026041L, 60},
				{4052739537881L, 6557470319842L, 64},
				{44945570212853L, 72723460248141L, 69},
				{498454011879264L, 806515533049393L, 74},
				{5527939700884757L, 8944394323791464L, 79},
				{61305790721611591L, 99194853094755497L, 84}
				
		};
		
		long[] cycles = new long[18];
		cycles[0] = 60;
		cycles[1] = 300;
		cycles[2] = 1500;
		
		for (int i = 3; i < cycles.length; i++) {
			cycles[i] = 15 * (long) Math.pow(10, i);
		}
		
		Scanner scanner = new Scanner(System.in);
		
		String digits = scanner.nextLine();
		
		scanner.close();

		int n = digits.length();
		long remainder = Long.valueOf(digits);
		
		
		boolean found = false;
		boolean localFound = false;
		
		MAIN: for (int i = 0; i <= n - 1; i++) {
			
			long f1 = fc[i][0];
			long f2 = fc[i][1];
			long startK = fc[i][2]; // position of fib
			
			long decimal = (int) Math.pow(10, i + 1);
			long localRemainder = remainder % decimal;
			
			LOCAL: for (long k = startK; k < cycles[i]; k++) {
				long f = (f1 + f2) % decimal;
				if (f == remainder) {
					System.out.println(k);
					found = true;
					break MAIN;
				}
				if (f == localRemainder) {
					localFound = true;
					break LOCAL;
				}
				f1 = f2;
				f2 = f;
			}
			if (!localFound) {
				break MAIN;
			}
		}
			
		if (!found) {
			System.out.println("NIE");
		}
		
	}
	
}