#include <bits/stdc++.h>
using namespace std;
class point {
 public:
  int id, val;
};
bool operator<(const point &a, const point &b) {
  if (a.val < b.val) return true;
  return false;
}
const long long maxn = (long long)1e18;
int i, t, v, len, col;
long long n;
long long f[101], dp[101][3][3];
int a[101];
long long rec(int i, int p, int q) {
  if (i == 0) return 1;
  if (dp[i][p][q] != -1) return dp[i][p][q];
  long long x = 0;
  int val = p + a[i];
  if (val <= 1) x = rec(i - 1, q, 0);
  if ((val > 0) && (i > 2)) x += rec(i - 1, q + 1, 1);
  dp[i][p][q] = x;
  return dp[i][p][q];
}
int main() {
  f[1] = 1;
  f[2] = 2;
  i = 2;
  while (f[i] + f[i - 1] <= maxn) {
    i++;
    f[i] = f[i - 1] + f[i - 2];
  }
  col = i;
  cin >> t;
  for (v = 1; v <= t; v++) {
    cin >> n;
    len = col;
    while (f[len] > n) len--;
    for (i = len; i >= 1; i--) {
      if (f[i] <= n) {
        a[i] = 1;
        n -= f[i];
      } else
        a[i] = 0;
    }
    memset(dp, -1, sizeof(dp));
    cout << rec(len, 0, 0) << endl;
  }
  return 0;
}
