#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 100;
int fib[N], f[N][2];
int a[N], n;
void sol(){
    int x;cin >> x;
    n = 0;
    for(int i = 90;i;i--){
        if(x >= fib[i]){
            x -= fib[i];
            a[++n] = i;
        }
    }
    f[n][0] = (a[n] + 1) / 2 - 1, f[n][1] = 1;
    for(int i = n - 1;i;i--){
        int c = a[i] - a[i + 1];
        f[i][0] = c / 2 * f[i + 1][0] + ((c + 1) / 2 - 1) * f[i + 1][1];
        f[i][1] = f[i + 1][0] + f[i + 1][1];
    }
    cout << f[1][0] + f[1][1] << endl;
}
int32_t main(){
    fib[1] = 1, fib[2] = 2;
    for(int i = 3;i <= 90;i++) fib[i] = fib[i - 1] + fib[i - 2];
    int cas;cin >> cas;while(cas--) sol();
    return 0;
}