#include <bits/stdc++.h>
using namespace std;
long long f[101], n;
long long g[101][2];
vector<long long> v;
int T;
int main() {
  f[1] = 1LL, f[2] = 2LL;
  for (int i(3); i <= (89); ++i) f[i] = f[i - 1] + f[i - 2];
  scanf("%d", &T);
  while (T--) {
    v.clear();
    scanf("%lld", &n);
    for (int i(89); i >= (1); --i) {
      if (f[i] <= n) {
        v.push_back(i);
        n -= f[i];
      }
    }
    reverse(v.begin(), v.end());
    g[0][0] = 1LL;
    g[0][1] = (v[0] - 1) / 2;
    for (long long i = 1; i < (int)v.size(); ++i) {
      g[i][0] = g[i - 1][0] + g[i - 1][1];
      g[i][1] = g[i - 1][0] * ((v[i] - v[i - 1] - 1) / 2) +
                g[i - 1][1] * ((v[i] - v[i - 1]) / 2);
    }
    printf("%lld\n", g[(int)v.size() - 1][0] + g[(int)v.size() - 1][1]);
  }
  return 0;
}
