#include <bits/stdc++.h>
using namespace std;
template <class x>
vector<typename x::value_type> tovec(const x& a) {
  return vector<typename x::value_type>(a.begin(), a.end());
}
template <class u>
vector<typename iterator_traits<u>::value_type> tovec(u a, u b) {
  return vector<typename iterator_traits<u>::value_type>(a, b);
}
template <typename x>
ostream& operator<<(ostream& cout, const vector<x>& a) {
  cout << "[";
  if (((int)a.size())) cout << a[0];
  for (int i = 0; i++ < ((int)a.size()) - 1;) cout << ", " << a[i];
  return cout << "]";
}
template <typename u, typename v>
ostream& operator<<(ostream& cout, const pair<u, v>& a) {
  return cout << "(" << a.first << ", " << a.second << ")";
}
vector<long long> fib;
void calfib() {
  fib.push_back(1);
  fib.push_back(2);
  while (fib.back() <= ((long long)1e18))
    fib.push_back(fib.back() + fib[((int)fib.size()) - 2]);
}
long long dp[90][2];
vector<long long> s;
long long cal(int i, bool keep) {
  if (i == ((int)s.size()) - 1) return keep;
  if (dp[i][keep] != -1) return dp[i][keep];
  if (keep)
    dp[i][keep] = cal(i + 1, 0) + cal(i + 1, 1);
  else
    dp[i][keep] = cal(i + 1, 1) * ((s[i] - s[i + 1] - 1) / 2) +
                  cal(i + 1, 0) * ((s[i] - s[i + 1]) / 2);
  return dp[i][keep];
}
int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  calfib();
  int n;
  cin >> n;
  while (n--) {
    long long a;
    cin >> a;
    s.clear();
    for (int i = ((int)fib.size()); i--;) {
      if (a >= fib[i]) {
        s.push_back(i);
        a -= fib[i];
      }
    }
    memset(dp, -1, sizeof(dp));
    s.push_back(-1);
    cout << cal(0, 0) + cal(0, 1) << '\n';
  }
  return 0;
}
