#include <bits/stdc++.h>

using namespace std;

typedef long long i64;

int T, n;
i64 N, f[100];

int main() {
    f[1] = 1, f[2] = 2;
    for (n = 3; ; n ++) {
        f[n] = f[n - 1] + f[n - 2];
        if (f[n] > 1e18) break;
    }
    for (scanf("%d", &T); T --; ) {
        scanf("%lld", &N);
        i64 a0 = 1, a1 = 0, b0, b1;
        for (int i = n, j = -1; i >= 0; i --) {
            if (N < f[i]) continue;
            N -= f[i];
            if (j != -1) {
                int d = j - i;
                b0 = a0 * (d + 1 >> 1) + a1 * (d - 1 >> 1);
                b1 = ~d & 1 ? a0 + a1 : 0;
                a0 = b0, a1 = b1;
            }
            j = i;
        }
        printf("%lld\n", a0);
    }
    return 0;
}