#include <bits/stdc++.h>
using namespace std;
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &t) {
  os << "[";
  for (__typeof((t).begin()) it = (t).begin(); it != (t).end(); it++) {
    if (it != t.begin()) os << ",";
    os << *it;
  }
  os << "]";
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &t) {
  os << "{";
  for (__typeof((t).begin()) it = (t).begin(); it != (t).end(); it++) {
    if (it != t.begin()) os << ",";
    os << *it;
  }
  os << "}";
  return os;
}
template <class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &t) {
  return os << "(" << t.first << "," << t.second << ")";
}
const int INF = 1 << 28;
const double EPS = 1e-8;
const int MOD = 1000000007;
long long int n;
int T;
int main() {
  vector<long long int> fib;
  long long int a = 1, b = 0;
  while (a + b <= 1000000000000000000LL) {
    fib.push_back(a + b);
    a = a + b;
    b = a - b;
  }
  cin >> T;
  for (int t = 0; t < (int)(T); t++) {
    cin >> n;
    vector<int> tbl(1);
    for (int i = ((int)(fib.size()) - 1); i >= 0; i--)
      if (n >= fib[i]) {
        n -= fib[i];
        tbl.push_back(i + 1);
      }
    sort(tbl.begin(), tbl.end());
    vector<int> dp0(tbl.size());
    vector<int> dp1(tbl.size());
    dp1[0] = 1;
    for (int i = 0; i < (int)(tbl.size()); i++) {
      if (!i) continue;
      dp1[i] += dp0[i - 1] + dp1[i - 1];
      dp0[i] += ((tbl[i] - tbl[i - 1] - 1) / 2) * (dp1[i - 1] + dp0[i - 1]);
      dp0[i] += ((tbl[i] - tbl[i - 1] - 1) % 2) * dp0[i - 1];
    }
    cout << (dp1.back() + dp0.back()) << endl;
  }
  return 0;
}
