the fibonacci sequence is defined by the recurrence relation fn fn1 fn2 where f1 1 and f2 1 hence the first 12 terms will be f1 1 f2 1 f3 2 f4 3 f5 5 f6 8 f7 13 f8 21 f9 34 f10 55 f11 89 f12 144 the 12th term f12 is the first term to contain three digits what is the index of the first term in the fibonacci sequence to contain 1000 digits computes the fibonacci number for input n by iterating through n numbers and creating an array of ints using the fibonacci formula returns the nth element of the array fibonacci2 1 fibonacci3 2 fibonacci5 5 fibonacci10 55 fibonacci12 144 computes incrementing fibonacci numbers starting from 3 until the length of the resulting fibonacci result is the input value n returns the term of the fibonacci sequence where this occurs fibonaccidigitsindex1000 4782 fibonaccidigitsindex100 476 fibonaccidigitsindex50 237 fibonaccidigitsindex3 12 returns the index of the first term in the fibonacci sequence to contain n digits solution1000 4782 solution100 476 solution50 237 solution3 12 computes the fibonacci number for input n by iterating through n numbers and creating an array of ints using the fibonacci formula returns the nth element of the array fibonacci 2 1 fibonacci 3 2 fibonacci 5 5 fibonacci 10 55 fibonacci 12 144 computes incrementing fibonacci numbers starting from 3 until the length of the resulting fibonacci result is the input value n returns the term of the fibonacci sequence where this occurs fibonacci_digits_index 1000 4782 fibonacci_digits_index 100 476 fibonacci_digits_index 50 237 fibonacci_digits_index 3 12 returns the index of the first term in the fibonacci sequence to contain n digits solution 1000 4782 solution 100 476 solution 50 237 solution 3 12
def fibonacci(n: int) -> int:
    
    if n == 1 or not isinstance(n, int):
        return 0
    elif n == 2:
        return 1
    else:
        sequence = [0, 1]
        for i in range(2, n + 1):
            sequence.append(sequence[i - 1] + sequence[i - 2])

        return sequence[n]


def fibonacci_digits_index(n: int) -> int:
    
    digits = 0
    index = 2

    while digits < n:
        index += 1
        digits = len(str(fibonacci(index)))

    return index


def solution(n: int = 1000) -> int:
    
    return fibonacci_digits_index(n)


if __name__ == "__main__":
    print(solution(int(str(input()).strip())))