import sys
sys.set_int_max_str_digits(5010)
from decimal import *
import random

def fib():
    a, b = 1, 1
    while ...:
        yield a
        a, b = b, a+b

def main():
    # preload n[digits]
    n = [0]
    lastd = 0
    for i, f in enumerate(fib(), 1):
        d = len(str(f))
        if d > lastd:
            lastd = d
            n.append(i)
            if d == 5000: break
            # if d == 50: break
    # do queries
    r5 = Decimal(5**.5)
    lphi = Decimal((1+r5)/2).ln()
    
    for _ in range(int(input())):
        q = int(input())
        n_formula = (r5 * 10**(q-1)).ln() / lphi
        print( random.choice([
            n_formula.to_integral_value(rounding = ROUND_CEILING),
            n[q]
        ]))

main()