#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;
const double PI = acos(-1);
const int oo = 1e9, bpr = 1e9 + 7, N = 0;
long long f[110];
int a[110];
long long d[110][4][4];
int n;
inline long long calc(int ps, int v1, int v2) {
  if (ps == n) return v1 == 0 && v2 == 0;
  if (d[ps][v1][v2] != -1) return d[ps][v1][v2];
  long long res = 0;
  for (int i = 0; i < 2; ++i) {
    int x = min(v1, v2 + i);
    for (int j = 0; j <= x; ++j) {
      if (v1 - j == a[ps]) {
        res += calc(ps + 1, v2 + i - j, j);
      }
    }
  }
  return d[ps][v1][v2] = res;
}
int main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  f[0] = f[1] = 1;
  for (n = 2; f[n - 1] <= 1e18; ++n) f[n] = f[n - 1] + f[n - 2];
  --n;
  int t;
  cin >> t;
  while (t--) {
    long long x;
    cin >> x;
    int cnt = 0;
    for (int i = n; i >= 1; --i) {
      a[i] = (f[i] <= x);
      if (a[i]) x -= f[i];
    }
    memset(d, -1, sizeof(d));
    cout << calc(0, 0, 0) << "\n";
  }
  return 0;
}
