#include <bits/stdc++.h>
using namespace std;
map<int, int> f;
long long fib[100] = {0};
int solve(long long n) {
  int what[100] = {0};
  int ind = -1;
  for (int i = 90; i >= 0; i--) {
    if (n >= fib[i]) {
      n -= fib[i], what[i] = true;
      if (ind == -1) ind = i;
    }
  }
  vector<int> x, y;
  x.push_back(1);
  y.push_back(0);
  int zero = 0, f = 1;
  for (int i = 0; i <= ind; i++) {
    if (what[i] == 0)
      zero++;
    else {
      int z1 = (zero / 2) * (x.back() + y.back());
      if (zero & 1 && !f) z1 += x.back();
      int z2 = x.back() + y.back();
      x.push_back(z1);
      y.push_back(z2);
      zero = 0;
      f = false;
    }
  }
  return x.back() + y.back();
}
int main() {
  fib[0] = 1;
  fib[1] = 2;
  for (int i = 2; i <= 90; i++) fib[i] = fib[i - 1] + fib[i - 2];
  int T;
  long long n;
  cin >> T;
  while (T--) {
    cin >> n;
    cout << solve(n) << endl;
  }
  return 0;
}
