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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import java.util.Random;
import java.util.Scanner;
import static java.lang.Math.*;
public class fib {
	long[]powers;
	long[]per;
	fib() {
		powers = new long[19];powers[0]=1;
		per = new long[19];
		per[1]=60;
		per[2]=300;
		per[3]=1500;
		for(int i=4;i<per.length;i++)per[i]=10*per[i-1];
		for(int i=1;i<powers.length;i++)powers[i]=10*powers[i-1];
	}
	
	  
		static long mulmod(long a, long b,long mod){    
		    long x = 0,y=a;
		    long t;   
		    while(b !=0){
		        if((b & 1) !=0){
		            t = x+y;
		            x = (t>mod) ? t-mod : t;
		        }
		        t = y<<1;
		        y = (t>mod) ? t-mod : t;        
		        b >>=1;
		    }
		    return x;    
		}
	
	static long pow(long k, long mod){
		if( k== 1)return 1;
		long xa = 0;long xb = 1;long xd=1;
		long ya=1;long yb=0;long yd=1;
		while(k >1) {
			if((k&1)==1) {
				long ybxb= mulmod(yb,xb,mod);
				long na = (mulmod(ya, xa,mod) + ybxb)%mod;
				long nb = (mulmod(ya,xb,mod) + mulmod(yb,xd,mod))%mod;
				long nd = (ybxb + mulmod(yd, xd,mod))%mod;
				ya=na;yb=nb;yd=nd;		}
			long na=(mulmod(xa,xa,mod) +mulmod(xb,xb,mod))%mod;
			long nb=mulmod((xa+xd)%mod,xb,mod);
			long nd=(mulmod(xb,xb,mod) +mulmod(xd,xd,mod))%mod;
			xa=na;xb=nb;xd=nd;
			k /=2;
		}
       return (mulmod(yb,xa,mod) + mulmod(yd, xb,mod))%mod;
	}

	static long calls =0;
	long getFib(long k, long mod) {
		calls++;
		long mm = pow(k, mod);
		return mm;
	}
	
	long search(long myEnd, int p, long offset, int prevP) {
		if(p==prevP)return offset;
		int currentP = min(p, prevP+2);
		long searching = myEnd % powers[currentP];
		for(int i=0;i<per[currentP]/per[prevP];i++) {
			long idx = offset + i * per[prevP];
			long fib = getFib(idx, powers[currentP]);
			if(fib==searching) {
				long r = search(myEnd, p, idx, currentP);
				if(r>-1)return r;
			}
		}
		return -1;
	}
	
	String doit(long myEnd, int p) {
		if(p==1 && myEnd <2)return myEnd+"";
		long a =0,b=1;
		int firstP = min(7, p);
		long searching = myEnd % powers[firstP];
		for(int i=2;i<per[firstP];i++) {
			long fib = (a+b)%powers[firstP];
			a=b;b=fib;
			if(fib==searching) {
				if(firstP==p) {
					return ""+i;
				} else {
					long res = search(myEnd, p, i, firstP);
					if(res!=-1){
						return ""+res;
					}
				}
			}
		}
		return "NIE";
	}
	
	static Random rand = new Random(0);
	static String randString(int len) {
		String res = "";
		long l =abs(rand.nextLong())%1000000000000000000L;
		long ff = new fib().getFib(l, 10000000000L);
		res =""+ff;
		while(res.length()<len)res=rand.nextInt(10)+res;;
		return res;
	}
	
public static void main(String[] args) {
	Scanner s = new Scanner(System.in);
	String digs = s.next();
	
	int len = digs.length();
	long val = Long.parseLong(digs);
	long startTime = System.currentTimeMillis();
	String res = new fib().doit(val, len);
	System.out.println(res);
	System.err.println("Time: "+(System.currentTimeMillis()-startTime));
	System.err.println("Calls "+calls);
	
	
}
}