#include <bits/stdc++.h>
using namespace std;
template <class T, class IT>
inline void PRINT(IT i1, IT i2) {
  cout << '[';
  copy(i1, i2, ostream_iterator<T>(cout, ", "));
  cout << "]\n";
}
long long fib[88 + 1];
long long solve(long long n) {
  bool n_fib[88 + 1];
  for (int i = 88; i >= 1; --i) {
    if (n >= fib[i]) {
      n_fib[i] = true;
      n -= fib[i];
    } else {
      n_fib[i] = false;
    }
  }
  int dist = 0;
  long long taken = 1;
  long long not_taken = 0;
  for (int i = (int)(1); i < (int)(88 + 1); ++i) {
    ++dist;
    if (n_fib[i]) {
      long long taken1 = taken + not_taken;
      long long not_taken1 = taken * ((dist - 1) / 2) + not_taken * (dist / 2);
      taken = taken1;
      not_taken = not_taken1;
      dist = 0;
    }
  }
  return taken + not_taken;
  ;
}
int main() {
  fib[1] = 1;
  fib[2] = 2;
  for (int i = (int)(3); i < (int)(88 + 1); ++i)
    fib[i] = fib[i - 1] + fib[i - 2];
  int tests;
  long long n;
  cin >> tests;
  while (tests--) {
    cin >> n;
    cout << solve(n) << '\n';
  }
  return 0;
}
