#include <bits/stdc++.h>
using namespace std;
const int maxx = 90, maxn = 1e2 + 20;
long long n, k, fib[maxx], sum = 0, dp_baste[maxx], dp_baz[maxx];
vector<int> v;
long long str(long long n) {
  v.clear();
  while (n) {
    int r = upper_bound(fib, fib + maxx, n) - fib;
    r--;
    v.push_back(r);
    n -= fib[r];
  }
  v.push_back(-1);
  reverse(v.begin(), v.end());
  dp_baz[0] = 0;
  dp_baste[0] = 1;
  for (int i = 1; i < v.size(); i++) {
    dp_baste[i] = dp_baste[i - 1] + dp_baz[i - 1];
    dp_baz[i] = (dp_baste[i - 1] * ((v[i] - v[i - 1] - 1) / 2)) +
                (dp_baz[i - 1] * ((v[i] - v[i - 1]) / 2));
  }
  return dp_baz[v.size() - 1] + dp_baste[v.size() - 1];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  fib[0] = 1;
  fib[1] = 2;
  for (int i = 0; i < maxx; i++) {
    if (i > 1) fib[i] = fib[i - 1] + fib[i - 2];
  }
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> k;
    cout << str(k) << "\n";
  }
  return 0;
}
