#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int MN=100;
ll f[MN],n,len,dp[MN][2],a[MN],cnt;
bool b[MN];
void write(ll n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
void init(){f[1]=f[2]=1;for(int i=3; i<=90; i++) f[i]=f[i-1]+f[i-2];}
void solve(){
    n=read();memset(b,false,sizeof(b));int i=90;cnt=len=0;
    while(n&&i--) if(n>=f[i]) n-=f[i],b[i]=true;
    for(int i=2; i<=90; i++){
        if(b[i]) a[++len]=cnt,cnt=0;
        else cnt++;
    }
    dp[1][0]=1;dp[1][1]=a[1]>>1;
    for(int i=2; i<=len; i++){
        dp[i][0]=dp[i-1][0]+dp[i-1][1];
        dp[i][1]=dp[i-1][0]*(a[i]>>1)+dp[i-1][1]*((a[i]+1)>>1);
    }
    write(dp[len][0]+dp[len][1]);putchar('\n');
}
int main(){
    init();
    ll T=read();while(T--)solve();
    return 0;
}