#include<bits/stdc++.h>
using namespace std;
#define int long long
struct HashFunc
{
    template<typename T, typename U>
    size_t operator()(const std::pair<T, U>& p) const {
    return std::hash<T>()(p.first) ^ std::hash<U>()(p.second);
    }
};
struct EqualKey {
    template<typename T, typename U>
    bool operator ()(const std::pair<T, U>& p1, const std::pair<T, U>& p2) const {
    return p1.first == p2.first && p1.second == p2.second;
    }
};
unordered_map<pair<int,int>,int,HashFunc,EqualKey>mp;
int a[105],pre[105];int pos=  88;
inline int dfs(int now,int pos){
	if(now == 0)return 1;
	if(pos == 0 and now!=0)return 0;
	if(pos<=80 and now>pre[pos])return 0;
//	cout <<now <<" " <<pos << endl;
	if(mp[{now,pos}])return mp[{now,pos}];
	int res =0 ;
	if(now>=a[pos])res+=dfs(now-a[pos],min(pos-1,(int)(upper_bound(a+1,a+89,now-a[pos])-a-1)));
	res+=dfs(now,pos-1);return mp[{now,pos}] = res;
	//return res;
}
signed main(){
	srand(time(0));
	a[1] = 1,a[2] = 2;mt19937 myrand(time(0));
	for(int i = 3;i<=88;i++)a[i] = a[i-1]+a[i-2];
	for(int i = 1;i<=88;i++)pre[i] = pre[i-1]+a[i];
	int t = 1000;cin >> t;
	while(t--){
		int n;cin >> n;
	//	n = (long long)myrand()*rand()*rand();
		//cout << n<< endl;
		cout << dfs(n,upper_bound(a+1,a+89,n)-a-1) << endl;
	}
	
	return 0;
}