#include <bits/stdc++.h>
using namespace std;
const int MAXN = 92;
const int MAXK = 1e5 + 5;
int t;
long long fib[MAXN];
int k;
long long n[MAXK];
bool bl[MAXN];
long long T[MAXN][MAXN];
int first;
void get_number(long long x) {
  for (int i = 0; i <= first; i++) {
    bl[i] = false;
  }
  first = 0;
  memset(T, -1, sizeof(T));
  for (int i = k - 1; i >= 0; i--) {
    if (fib[i] <= x) {
      first = max(first, i);
      x -= fib[i];
      bl[i + 1] = true;
    }
  }
  first++;
}
long long rec(int index, int prev) {
  if (index > first) return 1;
  if (T[index][prev] != -1) {
    return T[index][prev];
  }
  long long ans = 0;
  long long dist = (index - prev - 1);
  if (bl[index] == 1 && dist >= 2) {
    ans += rec(index + 1, index - 1) * (dist / 2);
  }
  if (bl[index] == 1) {
    ans += rec(index + 1, index);
  } else {
    ans += rec(index + 1, prev);
  }
  return T[index][prev] = ans;
}
void read_input() {
  scanf("%d", &t);
  long long v, z = 0;
  for (int i = 0; i < t; i++) {
    scanf("%I64d", &v);
    n[i] = v;
    z = max(z, v);
  }
  fib[k++] = 1;
  fib[k++] = 2;
  while (fib[k - 1] + fib[k - 2] <= z) {
    fib[k] = fib[k - 1] + fib[k - 2];
    k++;
  }
}
void solve() {
  for (int i = 0; i < t; i++) {
    get_number(n[i]);
    printf("%I64d\n", rec(1, 0));
  }
}
int main() {
  read_input();
  solve();
  return 0;
}
