#include <bits/stdc++.h>
using namespace std;
template <class T>
T abs(T x) {
  return x > 0 ? x : (-x);
}
template <class T>
T sqr(T x) {
  return x * x;
}
const long long inf = (long long)(2E18);
vector<long long> f;
long long calcR(long long n, int ind) {
  if (n == 0) return 1;
  if (ind < 0) return 0;
  if (f[ind] > n) return calcR(n, ind - 1);
  return calcR(n, ind - 1) + calcR(n - f[ind], ind - 1);
}
vector<int> v;
long long d[100][2][2];
long long go(int ind, int p1, int p2) {
  if (ind >= ((int)(v).size())) return 1;
  long long& res = d[ind][p1][p2];
  if (res != -1) return res;
  res = 0;
  res += go(ind + 1, p2, v[ind]);
  if (p1 && !p2) {
    if (!v[ind])
      res += go(ind + 1, 1, 1);
    else {
      int t = ind + 1;
      bool ok = false;
      while (t + 1 < ((int)(v).size())) {
        if (v[t] == 0 && v[t + 1] == 0) {
          ok = true;
          break;
        }
        if (v[t] == 1) break;
        t += 2;
      }
      if (ok) {
        res += go(t + 2, 1, 1);
      }
    }
  }
  return res;
}
int main() {
  f.push_back(1);
  f.push_back(2);
  while (f[((int)(f).size()) - 1] < inf) {
    f.push_back(f[((int)(f).size()) - 1] + f[((int)(f).size()) - 2]);
  }
  int nc;
  cin >> nc;
  for (int it = 0; it < nc; ++it) {
    long long n;
    cin >> n;
    v.clear();
    for (int i = ((int)(f).size()) - 1; i >= 0; --i) {
      if (f[i] > n) {
        if (((int)(v).size())) v.push_back(0);
        continue;
      }
      n -= f[i];
      v.push_back(1);
    }
    memset(d, -1, sizeof(d));
    long long res = go(0, 0, 0);
    cout << res << "\n";
  }
  return 0;
}
