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 a generator that produces numbers in the fibonacci sequence generator fibonaccigenerator nextgenerator 1 nextgenerator 2 nextgenerator 3 nextgenerator 5 nextgenerator 8 returns the index of the first term in the fibonacci sequence to contain n digits solution1000 4782 solution100 476 solution50 237 solution3 12 a generator that produces numbers in the fibonacci sequence generator fibonacci_generator next generator 1 next generator 2 next generator 3 next generator 5 next generator 8 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
from collections.abc import Generator


def fibonacci_generator() -> Generator[int, None, None]:
    
    a, b = 0, 1
    while True:
        a, b = b, a + b
        yield b


def solution(n: int = 1000) -> int:
    
    answer = 1
    gen = fibonacci_generator()
    while len(str(next(gen))) < n:
        answer += 1
    return answer + 1


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