import sys
sys.set_int_max_str_digits(5000)

def fibo_length():
    a, b = 0, 1
    memo = {}
    length = 1
    index = 1
    while length <= 5000:
        if len(str(b))==length:
            memo[length] = index
            length+=1
        a, b = b, a + b
        index+=1
    return memo

# memoized fibonacci element's length with thier index
memo = fibo_length()

t = int(input())
for _ in range(t):
    n = int(input())
    print(memo.get(n))