#include <bits/stdc++.h>
using namespace std;
long long a[60]; 
int main(){
    int q;
    cin>>q;
    a[1]=a[2]=1;
    for(int i=3;i<=50;i++){
        a[i]=a[i-1]+a[i-2];
        if(a[i]>1e9)break;
    }
    while (q--){
        int x;
        cin>>x;
        for(int i= 1;i<=50;i++){
            if(a[i]>x){
                cout<<a[i-1]<<endl;
                break;
            }
        }
    }
    return 0;
}