#include <bits/stdc++.h>

using namespace std;

#define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);

typedef long long LL;
typedef pair<int, int> PII;

const int N = 200010;
const int INF = 0x3f3f3f3f;

template<typename Type>
inline void read(Type &res)
{
    res = 0;
    int ch = getchar(), flag = 0;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }

int fib[100];
map<PII, int> dp;
bool vis[N];

int dfs(int cur, int idx)
{
    if (!cur) return 1;
    if (dp.count(PII(cur, idx))) return dp[PII(cur, idx)];
    int res = 0;

    // for (int i = 87; i >= 0; i --)
    for (int i = idx + 1; i <= 87; i ++)
        if (cur >= fib[i])
            res += dfs(cur - fib[i], i);
    return dp[PII(cur, idx)] = res;
}

signed main()
{
    fib[0] = fib[1] = 1;
    for (int i = 2; i < 90; i ++) fib[i] = fib[i - 1] + fib[i - 2];
    
    int T; read(T);
    while (T --)
    {
        int x; read(x);
        cout << dfs(x, 0) << '\n';
    }

    return 0;
}