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

public class fib {
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		String lng = scn.nextLine();
		BigInteger int1 = BigInteger.ZERO;
		BigInteger int2 = BigInteger.ONE;
		BigInteger tmp;
		int k = 2;
		while(true) {
			boolean ends = endsWith(lng, int1.add(int2));
			if(!ends && (int1.add(int2).compareTo(new BigInteger("10").pow(100)) == -1)) {
				tmp = int2;
				int2 = int2.add(int1);
				int1 = tmp;
				k++;
			} else {
				break;
			}
		}
		BigInteger res = new BigInteger("0").add(int1).add(int2);
		if(endsWith(lng,res))
			System.out.println(k);
		else
			System.out.println("NIE");
		scn.close();
	}
//	public static boolean endsWith(Long toEndWith, Long testThis) {
//		char[] testThis_ = testThis.toString().toCharArray();
//		char[] toEndWith_ = toEndWith.toString().toCharArray();
//		int chars_1 = toEndWith_.length;
//		boolean failed=false;
//		for(int i = testThis_.length - chars_1; i<= testThis_.length;i++) {
//			if(!(testThis_[i] == toEndWith_[i]))
//				failed=true;
//		}
//		return !failed;
//	}
	public static boolean endsWith(String end, BigInteger test) {
		String sub;
		try {
		sub = test.toString().substring(test.toString().length() - end.length());
		} catch (Exception e) {
			return false;
		}
		return sub.equals(end);
	}
}