#include <bits/stdc++.h>
using namespace std;
int f(int x);
int g(int x);
int nq, jwb, le;
vector<int> rep;
long long fib[100], n;
int memof[100], memog[100];
int f(int x) {
  if (x == 0) {
    return 1;
  } else if (memof[x] != -1) {
    return memof[x];
  } else {
    memof[x] = f(x - 1) + g(x - 1);
    return memof[x];
  }
}
int g(int x) {
  if (x == 0) {
    return 0;
  } else if (memog[x] != -1) {
    return memog[x];
  } else {
    memog[x] = f(x - 1) * ((rep[x] - rep[x - 1] - 1) / 2) +
               g(x - 1) * ((rep[x] - rep[x - 1]) / 2);
    return memog[x];
  }
}
int main() {
  fib[0] = 1;
  fib[1] = 2;
  for (int i = 2; i <= 99; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  long long dop;
  int p;
  cin >> nq;
  while (nq--) {
    cin >> n;
    rep.clear();
    dop = n;
    p = 90;
    while (p + 1) {
      if (fib[p] <= dop) {
        dop -= fib[p];
        rep.push_back(p);
      }
      p--;
    }
    rep.push_back(-1);
    reverse(rep.begin(), rep.end());
    memset(memof, -1, sizeof memof);
    memset(memog, -1, sizeof memog);
    printf("%d\n", f(rep.size() - 1) + g(rep.size() - 1));
  }
  return 0;
}
