#!/usr/bin/env python3

from math import sqrt, log10

def main():
    k = 1
    m    = 0
    last = 1
    gr    = (1 + sqrt(5)) / 2
    first = gr*(1/sqrt(5))
    while cond(str(int(first))[:9], str(last)):
        last, m = (last+m)%10**9, last
        first = gr*first
        if first >= 10**9:
            first /= 10
        k += 1
    return k, int(log10(gr)*k - log10(1/sqrt(5)) + 1/2.0)

def cond(first, last):
    a = len(set(last))  != 9
    b = len(set(first)) != 9
    c = '0' in first+last
    return a or b or c

print(main()[0])