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
 97
 98
 99
100
101
102
103
104
//package fib;

import java.math.BigInteger;
import java.util.Scanner;
import java.util.Vector;
import java.lang.Math;

public class fib {
	public static void main(String[] args) {
	Scanner in = new Scanner( System.in );
	//while(true)
	{
		int n;
		String ending;
		ending = in.nextLine();
		//System.out.println(ending);
		int len = ending.length();
		final String INF = "100000000000000000000000000000000000000000000000000000";
		//int start = 90;
		BigInteger cycle = new BigInteger("1"), newcycle = new BigInteger(INF);
		Vector<BigInteger> good = new Vector<BigInteger>(), newgood = new Vector<BigInteger>();
		newgood.add(new BigInteger("90"));
		BigInteger mod = new BigInteger("1");
		for (int i = len-1; i>=0; i--) {
			mod = mod.multiply(new BigInteger("10"));
			
			good = newgood;
			newgood = new Vector<BigInteger>();
			for (BigInteger b : good) {
				BigInteger Fb = count_fib(b, mod);
				BigInteger Fb1 = count_fib(b.add(new BigInteger("1")), mod);
				
				for (BigInteger t = b; ; t = t.add(cycle)) {
					BigInteger Ft = count_fib(t, mod);
					BigInteger Ft1 = count_fib(t.add(new BigInteger("1")), mod);
					if(Fb.equals(Ft) && Fb1.equals(Ft1) && !t.equals(b)) {
						BigInteger temp = t.subtract(b);
						if(temp.compareTo(newcycle) == -1) {
							newcycle = temp;
							//System.out.println(i + ": newcycle " + newcycle);
						}
						break;
					}
					if(Ft.equals( new BigInteger(ending.substring(i, len))))
					{
						//System.out.println("yay " + t);
						newgood.add(t);
					}
					
				}
			}
			cycle = newcycle;
			newcycle = new BigInteger(INF);
		}
		if(newgood.isEmpty())
			System.out.println("NIE");
		else
			System.out.println(newgood.get(0));
	}
	}

	private static BigInteger count_fib(BigInteger b, BigInteger mod) {
		
		BigInteger[][] m = new BigInteger[2][2];
		m[0][0] = m[0][1] = m[1][0] = new BigInteger("1");
		m[1][1] = new BigInteger("0");
		power(m, b, mod);
		//System.out.println("F[ " + b + " ] = " + m[1][0]);
		return m[1][0];
	}

	private static void power(BigInteger[][] m, BigInteger b, BigInteger mod) {
		
		if(b.equals(BigInteger.ONE))
			return;
		power(m, b.divide(new BigInteger("2")), mod);
		multiply(m, m, mod);
		if(b.mod(new BigInteger("2")).equals(new BigInteger("1"))){
			BigInteger[][] base = new BigInteger[2][2];
			base[0][0] = base[0][1] = base[1][0] = new BigInteger("1");
			base[1][1] = new BigInteger("0");
			multiply(m, base, mod);
		}
	}

	private static void multiply(BigInteger[][] a, BigInteger[][] b, BigInteger mod) {
		BigInteger[][] res = new BigInteger[2][2];
		res[0][0] = a[0][0].multiply(b[0][0]) .add ( a[0][1].multiply(b[1][0]));
		res[0][1] = a[0][0].multiply(b[0][1]) .add ( a[0][1].multiply(b[1][1]));
		res[1][0] = a[1][0].multiply(b[0][0]) .add ( a[1][1].multiply(b[1][0]));
		res[1][1] = a[1][0].multiply(b[0][1]) .add ( a[1][1].multiply(b[1][1]));
		if(mod != null) {
			a[0][0] = res[0][0].mod(mod);
			a[1][0] = res[1][0].mod(mod);
			a[0][1] = res[0][1].mod(mod);
			a[1][1] = res[1][1].mod(mod);
		} else {
			a[0][0] = res[0][0];
			a[1][0] = res[1][0];
			a[0][1] = res[0][1];
			a[1][1] = res[1][1];
		}
	}
}