#include <bits/stdc++.h>
#pragma hdrstop
using namespace std;
void solve();
int main() {
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}
long long n;
vector<long long> fib;
vector<long long> one;
vector<long long> dp1, dp2;
void solve() {
  cin >> n;
  if (n < 3) {
    cout << "1\n";
    return;
  }
  fib.resize(0);
  dp1.resize(0);
  dp2.resize(0);
  one.resize(0);
  fib.push_back(1);
  fib.push_back(2);
  while (fib[fib.size() - 1] + fib[fib.size() - 2] <= n)
    fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
  long long m = n;
  for (long long i = fib.size() - 1; i >= 0 && m > 0; i--)
    if (m >= fib[i]) {
      one.push_back(i);
      m -= fib[i];
    }
  one.push_back(-1);
  sort(one.begin(), one.end());
  dp1.resize(one.size() + 1);
  dp2.resize(one.size() + 1);
  dp1[0] = 1;
  dp2[0] = 0;
  for (long long i = 0; i < one.size() - 1; i++) {
    dp1[i + 1] = dp1[i] + dp2[i];
    dp2[i + 1] = dp1[i] * ((one[i + 1] - one[i] - 1) / 2) +
                 dp2[i] * ((one[i + 1] - one[i]) / 2);
  }
  cout << dp1[one.size() - 1] + dp2[one.size() - 1] << endl;
}
