#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 4e18;
const long long MAX = 1e5;
const long long MV = 1e18;
const long double PI = 3.14159265358979323846;
long long MA = -INF, MI = INF;
long long PO(long long x, long long y) {
  if (y == 0) return 1;
  long long ans = PO(x, y / 2);
  ans *= ans, ans %= MOD;
  if (y % 2 == 1) ans *= x, ans %= MOD;
  return ans % MOD;
}
void RE(long long x) {
  x %= MOD;
  if (x < 0) x += MOD;
}
long long fib[100], dp1[100], dp2[100], siz = 2;
void cal() {
  fib[1] = 1, fib[2] = 2;
  while (true) {
    long long temp = fib[siz - 1] + fib[siz];
    if (temp > MV)
      break;
    else
      fib[++siz] = temp;
  }
}
int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),
      cout << fixed << setprecision(10);
  cal();
  long long t;
  cin >> t;
  deque<long long> rep;
  while (t--) {
    long long n;
    cin >> n;
    for (long long i = siz; i >= 1; i--) {
      if (n >= fib[i]) rep.push_back(i), n -= fib[i];
    }
    reverse(rep.begin(), rep.end());
    rep.push_front(0);
    long long len = rep.size();
    dp1[0] = 1;
    dp2[0] = 0;
    for (long long i = 1; i < len; i++) {
      dp1[i] = dp1[i - 1] + dp2[i - 1];
      dp2[i] = (dp1[i - 1] * ((rep[i] - rep[i - 1] - 1) / 2)) +
               (dp2[i - 1] * ((rep[i] - rep[i - 1]) / 2));
    }
    cout << dp1[len - 1] + dp2[len - 1] << "\n";
    rep.clear();
  }
  return 0;
}
