#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 1;
const int INF = 1e9 + 9;
const int B = 1e9 + 7;
int sz;
long long f[N];
long long d[N][2];
int main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  f[0] = 1, f[1] = 1;
  for (sz = 2;; ++sz) {
    f[sz] = f[sz - 2] + f[sz - 1];
    if (f[sz] > 1e18) break;
  }
  int tests;
  cin >> tests;
  for (int test = int(1); test <= int(tests); ++test) {
    long long n;
    cin >> n;
    vector<int> v;
    for (int i = int(sz); i >= int(1); --i) {
      if (n >= f[i]) {
        v.push_back(i);
        n -= f[i];
      }
    }
    v.push_back(0);
    reverse(v.begin(), v.end());
    memset(d, 0, sizeof d);
    d[0][1] = 1;
    for (int i = int(1); i <= int(v.size() - 1); ++i) {
      d[i][1] = d[i - 1][0] + d[i - 1][1];
      int dist = v[i] - v[i - 1];
      d[i][0] = d[i - 1][0] * (dist / 2) + d[i - 1][1] * ((dist - 1) / 2);
    }
    cout << d[v.size() - 1][0] + d[v.size() - 1][1] << "\n";
  }
  return 0;
}
