// Problem: D. 8.4t3
// Contest: undefined - NOIP2024训练赛 12
// URL: http://noi.ac/contest/1164/problem/2733
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PII pair<int, int>

using namespace std;

const int N = 2e5 + 10, M = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;

int n, m, q, ans;
int dp[N][70], sum[80];

vector<int> v;

inline void init()
{
	memset(dp, -1, sizeof dp); v.push_back(0);
	for(int i = 0; i <= 65; i ++) dp[0][i] = 1;
	int a = 1, b = 1; v.push_back(1);
	while(1)
	{
		int c = a + b; if(c > 1e18) break; 
		v.push_back(c), a = b, b = c;
	}
	for(int i = 1; i <= 50; i ++) sum[i] = sum[i - 1] + v[i];
}

int dfs(int now, int flag)
{
	// if(!now) return 1;
	if(flag <= 50 && now > sum[flag - 1]) return 0;
	if(now <= 200000 && ~dp[now][flag]) return dp[now][flag];
	int res = 0;
	for(int i = flag - 1; ~ i; i --)
	{
		if(v[i] > now) continue;
		res += dfs(now - v[i], i);
	}
	if(now <= 200000) dp[now][flag] = res;
	return res;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	init();
	int T; cin >> T;
	while(T --)
	{
		cin >> n;
		cout << dfs(n, v.size()) << '\n';
	}
	return 0;
}