def solution() -> int:

    a = 1
    b = 1
    c = 2
    # temporary Fibonacci numbers

    a1 = 1
    b1 = 1
    c1 = 2
    # temporary Fibonacci numbers mod 1e9

    # mod m=1e9, done for fast optimisation
    tocheck = [0] * 1000000
    m = 1000000000

    for x in range(1000000):
        c1 = (a1 + b1) % m
        a1 = b1 % m
        b1 = c1 % m
        if check1(b1):
            tocheck[x + 3] = 1

    for x in range(1000000):
        c = a + b
        a = b
        b = c
        # perform check only if in tocheck
        if tocheck[x + 3] and check(b):
            return x + 3  # first 2 already done
    return -1