#include <bits/stdc++.h>
using namespace std;
int CC;
long long f[109];
int v[109];
long long d0[109], d1[109];
int main() {
  f[1] = 1;
  f[2] = 2;
  CC = 2;
  while (f[CC - 1] + f[CC] < 1000 * 1000 * 1000LL * 1000LL * 1000 * 1000) {
    f[CC + 1] = f[CC] + f[CC - 1];
    CC++;
  }
  int T;
  for (scanf("%d", &T); T > 0; T--) {
    long long n;
    scanf("%lld", &n);
    memset(v, 0, sizeof v);
    int cnt = 0;
    for (int i = CC; i > 0 && n > 0; i--) {
      if (n - f[i] >= 0) n -= f[i], v[++cnt] = i;
    }
    reverse(v + 1, v + cnt + 1);
    d0[0] = 1, d1[0] = 0;
    for (int k = 1; k <= cnt; k++) {
      d0[k] = d0[k - 1] + d1[k - 1];
      d1[k] = 0;
      d1[k] += d0[k - 1] * ((v[k] - v[k - 1] - 1) / 2);
      d1[k] += d1[k - 1] * ((v[k] - v[k - 1]) / 2);
    }
    printf("%lld\n", d1[cnt] + d0[cnt]);
  }
  return 0;
}
