#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
vector<long long> fib = {1, 2};
map<pair<long long, long long>, long long> dp;
long long f(long long n, int j) {
  if (fib[j] > n) return 0;
  if (fib[j] == n) return 1;
  long long tot = 0;
  for (int j2 = 0; j2 < j; j2++) {
    tot += f(n - fib[j], j2);
  }
  return tot;
}
int f2(long long n) {
  int sz = fib.size();
  vector<bool> cur(sz);
  for (int i = sz - 1; i >= 0; i--) {
    if (n >= fib[i]) {
      cur[i] = 1;
      n -= fib[i];
    }
  }
  queue<vector<bool>> q;
  q.push(cur);
  int ans = 0;
  set<vector<bool>> vis;
  vis.insert(cur);
  while (q.size()) {
    ans++;
    cur = q.front();
    q.pop();
    for (int i = 2; i < sz; i++) {
      if (cur[i] && !cur[i - 1] && !cur[i - 2]) {
        auto cur2 = cur;
        cur2[i] = 0;
        cur2[i - 1] = 1;
        cur2[i - 2] = 1;
        auto it = vis.find(cur2);
        if (it == vis.end()) {
          vis.insert(cur2);
          q.push(cur2);
        }
      }
    }
  }
  return ans;
}
long long f3(long long n) {
  int sz = fib.size();
  vector<bool> cur(sz);
  vector<int> v;
  for (int i = sz - 1; i >= 0; i--) {
    if (n >= fib[i]) {
      cur[i] = 1;
      v.push_back(i);
      n -= fib[i];
    }
  }
  reverse(v.begin(), v.end());
  int m = v.size();
  vector<long long> dp1(m), dp2(m);
  dp1[0] = 1;
  dp2[0] = v[0] / 2;
  for (int i = 1; i < m; i++) {
    dp1[i] = dp1[i - 1] + dp2[i - 1];
    dp2[i] = ((v[i] - v[i - 1]) / 2) * dp2[i - 1] +
             ((v[i] - v[i - 1] - 1) / 2) * dp1[i - 1];
  }
  return dp1[m - 1] + dp2[m - 1];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  while (fib.back() < 1e18) {
    int n = fib.size();
    fib.push_back(fib[n - 1] + fib[n - 2]);
  }
  int t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    long long ans = 0;
    cout << f3(n) << '\n';
  }
  return 0;
}
