#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
const int N = 90;

int fib[N];
int f[N][2];

void init(){
    fib[0] = fib[1] = 1;
    for(int i = 2; i < N; i++) fib[i] = fib[i - 1] + fib[i - 2];
    //cout << fib[N - 1];
}

int v[N];

void solve(){
    memset(v, 0, sizeof(v));
    memset(f, 0, sizeof(f));
    int n;
    cin >> n;
    int cnt = 0;
    for(int i = 88; i >= 1; i--){
        if(n >= fib[i]) v[++cnt] = i, n -= fib[i];
    }
    reverse(v + 1, v + 1 + cnt);
    f[1][0] = (v[1] - 1) / 2, f[1][1] = 1;
    for(int i = 2; i <= cnt; i++){
        f[i][1] = f[i - 1][0] + f[i - 1][1];
        f[i][0] = f[i - 1][0] * ((v[i] - v[i - 1]) / 2) + f[i - 1][1] * ((v[i] - v[i - 1] - 1) / 2);
    }
    cout << f[cnt][0] + f[cnt][1] << '\n';
}

signed main(){
    init();
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}