#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long N = 88;
long long f[N];
void solve() {
  long long n;
  cin >> n;
  vector<long long> a(N);
  long long i = N - 1;
  while (i) {
    if (n >= f[i]) {
      n -= f[i];
      a.push_back(1);
    } else
      a.push_back(0);
    i--;
  }
  a.push_back(0);
  reverse(a.begin(), a.end());
  while (a.back() == 0) a.pop_back();
  long long k = (long long)a.size();
  vector<vector<long long>> dp;
  dp.push_back({1, 0, 1});
  long long s = 0;
  for (long long i = 1; i < k; i++) {
    if (a[i] == 0)
      s++;
    else {
      long long x = dp.back()[2];
      long long y = dp.back()[2] * (s / 2);
      if (s & 1) y += dp.back()[1];
      long long z = x + y;
      dp.push_back({x, y, z});
      s = 0;
    }
  }
  cout << dp.back()[2] << '\n';
}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  f[1] = 1;
  f[2] = 2;
  for (long long i = 3; i < N; i++) {
    f[i] = f[i - 1] + f[i - 2];
  }
  long long q;
  cin >> q;
  while (q--) {
    solve();
  }
}
