import sys
sys.set_int_max_str_digits(5000)
d={1:1,}
i,j=2,3
first,second=1,1
while i<=5000:
    first,second=second,first+second
    if len(str(second))==i and i not in d:
        d[i]=j
        i+=1
    j+=1
     
t=int(input().strip())
for _ in range(t):
    n=int(input().strip())
    print(d[n])

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()
        

#List a save the result
a = [0, 1, 7, 12, 17, 21, 26, 31, 36, 40, 45, 50, 55, 60, 64, 69, 74, 79, 84, 88, 93, 98, 103, 
 107, 112, 117, 122, 127, 131, 136, 141, 146, 151, 155, 160, 165, 170, 174, 179, 184, 189,
 194, 198, 203, 208, 213, 217, 222, 227, 232, 237, 241, 246, 251, 256, 261, 265, 270, 275,
 280, 284, 289, 294, 299, 304, 308, 313, 318, 323, 328, 332, 337, 342, 347, 351, 356, 361,
 366, 371, 375, 380, 385, 390, 395, 399, 404, 409, 414, 418, 423, 428, 433, 438, 442, 447,
 452, 457, 462, 466, 471]
 
t = int(input())
for i in range(t):
    n = int(input())

import java.io.*;
import java.util.*;
import java.math.*;

public class Solution {

    // public static void main(String[] args) {
    //     /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
    // }
    
//public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        // Scanner sc = new Scanner(System.in);
        // int n=sc.nextInt();
        // String str1;


        // for(int i=0;i<n;i++){
        //     int val=sc.nextInt();
        //     int cnt=0;    
        //     BigInteger a = BigInteger.valueOf(0); 
        //     BigInteger b = BigInteger.valueOf(1); 
        //     BigInteger c = BigInteger.valueOf(1); 

        // for (BigInteger bi = BigInteger.valueOf(1000000000000L);
        //     bi.compareTo(BigInteger.ZERO) > 0;
        //     bi = bi.add(BigInteger.ONE)){
            
        //     c =  a.add(b); 
        //     a = b; 
        //     b = c;
            
        //     str1 = a.toString();  
        //     cnt++;
            
        //     if(val==str1.length())
        //     break;  
        // } 
        // System.out.println(cnt);

        // }
        
public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            int a0 = in.nextInt();
            if (lastBitNum <= a0) {
                calc(a0);
            }
            System.out.println(result[a0]);
        }
        in.close();
    }

    static int LENGTH = 10000;

    static int DIGIT_NUMBER = 5001;

    static int[][] a = new int[2][DIGIT_NUMBER];

    static int[] result = new int[DIGIT_NUMBER];// store the result

    static int lastBitNum = 1;// digit N

    static int lastArrayIndex = 2;// which term

    /**
     * initial
     */
    static {
        a[0][0] = 1;
        a[1][0] = 1;
    }

    static void calc(int i) {
//        System.out.println(LocalDateTime.now());
        while (lastBitNum <= i) {
            lastArrayIndex = find(lastBitNum, lastArrayIndex);
//            System.out.println("lastBitNum : " + lastBitNum + " index : " + lastArrayIndex);
            lastBitNum++;
        }
//        System.out.println(LocalDateTime.now());
    }

    /**
     * 
     * @param lastBitNum
     * @param lastArrayIndex
     * @return
     */
    private static int find(int lastBitNum, int lastArrayIndex) {
        int[] tmp = new int[DIGIT_NUMBER];
        while (true) {
            tmp = nextFibonacciNum(a[0], a[1]);
            a[0] = a[1];
            a[1] = tmp;
            int bitNum = calcBit(tmp);
            lastArrayIndex++;
            if (bitNum == lastBitNum) {
                result[lastBitNum] = lastArrayIndex;
                return lastArrayIndex;
            }
        }
    }

    static int calcBit(int[] a) {
        int index = 0;
        for (int i = a.length - 1; i >= 0; i--) {
            if (a[i] > 0) {
                return i + 1;
            }
        }
        return index;
    }

    private static int[] nextFibonacciNum(int[] a, int[] b) {
        int[] c = new int[a.length];
        int carry = 0;
        for (int i = 0; i < DIGIT_NUMBER; i++) {
            int result = (a[i] + b[i] + carry);
            int remainder = result % 10;
            c[i] = remainder;
            carry = result / 10;
        }
        return c;
    }

    
}

import sys
sys.set_int_max_str_digits(6000)

li=[1,1]
answers=[0,1,]
x=2
max_len=1

# I simultaneously calculate the fibonacci numbers and set an answers list corresponding to the nth term which has digits >= that indice of the list
while max_len<5000:
    x+=1
    new_number=li[-2]+li[-1]
    length=len(str(new_number))
    li.append(new_number)
    if length>max_len:
        answers+=[x]*(length-max_len)
        max_len=length
        
for _ in range(int(input())):
    n=int(input())
    print(answers[n])