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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class fib {

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        System.out.println(run(input));
    }

    public static String run(BufferedReader input) throws IOException {
        String pattern = input.readLine();
        long MOD = (long) Math.pow(10, pattern.length());
        //long MAX = (long) Math.pow(5, pattern.length()+1) * 12;
        long i = 0;
        long prev = 0;
        long fib = 1;
        long tmp;
        while(i < 1000000) {
            if (i == 0) {
                fib = 0;
            }
            else if(i == 1) {
                fib = 1;
            }
            else {
                tmp = (prev % MOD + fib % MOD);
                prev = fib;
                fib = tmp;
            }
            if (Long.toString(fib).endsWith(pattern)) {
                return Long.toString(i);
            }
            ++i;
        }
        return "NIE";
    }

}