#include <bits/stdc++.h>
using namespace std;
const long long MAXI = 1e18;
vector<long long> fib;
void init() {
  long long a, b, c;
  a = 1;
  b = 2;
  fib.push_back(1);
  fib.push_back(2);
  while (a + b < MAXI) {
    c = a + b;
    a = b;
    b = c;
    fib.push_back(c);
  }
}
int ids[88];
long long ans[88];
long long query(long long x) {
  int sz = 0;
  for (int i = fib.size() - 1; i >= 0; i--) {
    if (x >= fib[i]) {
      ids[sz++] = i + 1;
      x -= fib[i];
    }
  }
  if (x) return 0;
  ids[sz++] = 0;
  reverse(ids, ids + sz);
  long long d;
  ans[0] = 1;
  ans[1] = 1;
  for (int i = 1; i < sz; i++) {
    d = (ids[i] - ids[i - 1]) / 2 + 1;
    ans[i + 1] = ans[i] * d;
    if ((ids[i] & 1) == (ids[i - 1] & 1)) ans[i + 1] -= ans[i - 1];
  }
  return ans[sz];
}
int main() {
  init();
  int nQ;
  long long val;
  scanf("%d\n", &nQ);
  for (int i = 0; i < nQ; i++) {
    scanf("%I64d", &val);
    printf("%I64d\n", query(val));
  }
  return 0;
}
