#include<bits/stdc++.h>

using namespace std;

string add(string a,string b){
    string c = "";
    a = string(b.length()-a.length(),'0') + a;
    //cout<<"a = "<<a<<"b = "<<b<<"\n";
    int carry = 0;
    for(int i=b.length()-1;i>=0;--i){
        int x = a[i]-'0',y = b[i]-'0';
        int z = x+y+carry;
        c = to_string(z%10) + c;
        carry = z/10;
    }
   if(carry){
       c = to_string(carry) + c;
   }
   return c;
}

int main(){
    vector<int >cache = {1};
    string a = "1",b = "1";
    int index = 2,prev = 1;
    while(cache.size() <= 5000){
        index++;
        string c = add(a,b);
        a = b;
        b = c;
      //  cout<<c<<"\n";

        int curr = c.length();
        if(curr > prev){
            cache.push_back(index);
        }
        prev = curr;
    }
    
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        cout<<cache[n-1]<<"\n";
    }
    return 0;
}