A fact: There exists a algorithm with time complexity linear to the no of testcases ie. O(1) per input.

Using binary search and printing the lower bound

from math import log, ceil
def numberOfDigits(n):
    if n==1:
        return 1
    ans = (n * log(1.6180339887498948, 10)) - ((log(5, 10)) / 2)
    return ceil(ans)

testcases = input()
while testcases:
    low, high = 0, 25000
    n = input()
    while low < high:
        mid = (low+high)/2
        mid_n = numberOfDigits(mid)
        if mid_n >= n:
            high = mid
        else:
            low = mid+1
    print((low+high)/2)
    testcases -= 1

Can easily be done using Python in ~3s for each TC without caring about integer length (because this is PAINFUL):

Memoization is the key here: Precompute fibonacci until you reach a number with 5000 digits DON'T SAVE ALL FIBO NUMBERS Save the fibo index each time you increase the max size You now have an array of 5000 elements (each containing the right index) in about 3 seconds

Hint : Use string length while searching for integer length

for each test case, just print array[test_case]

The closed-form formula is the best way to solve this problem. It can be inaccurate for calculating exact values of Fibonacci numbers, but we need to calculate log10 of a Fibonacci number here and particular accuracy is not needed. Basically log10(phi^k/sqrt(5)) + 1 is a good estimate for the number of digits of a Fibonacci number and this formula is easily simplified to a linear equation to find k.