#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 5;
const long long linf = 1e18 + 5;
const int N = 95;
int t, dp[N][2][2];
long long n, fib[N];
bool used[N];
int f(int x, bool w1, bool w2) {
  if (!x) return !w1 and !w2;
  int &r = dp[x][w1][w2];
  if (r != -1) return r;
  r = 0;
  if (!w1 and !w2 and !used[x]) r += f(x - 1, 0, 0);
  if (!w1 and !w2 and used[x]) r += f(x - 1, 0, 0) + f(x - 1, 1, 1);
  if (w1 and !w2 and !used[x]) r += f(x - 1, 0, 0) + f(x - 1, 1, 1);
  if (w1 and !w2 and used[x]) r += f(x - 1, 1, 1);
  if (w1 and w2 and !used[x]) r += f(x - 1, 1, 0);
  return r;
}
int main() {
  ios ::sync_with_stdio(0);
  fib[1] = 1;
  fib[2] = 2;
  for (int i = 3; i <= 91; i++) fib[i] = fib[i - 1] + fib[i - 2];
  cin >> t;
  for (int test = 1; test <= t; test++) {
    memset(used, 0, sizeof(used));
    memset(dp, -1, sizeof(dp));
    cin >> n;
    for (int i = 91; i >= 1; i--)
      if (n >= fib[i]) {
        used[i] = 1;
        n -= fib[i];
      }
    if (n) {
      cout << 0 << '\n';
      continue;
    }
    cout << f(91, 0, 0) << '\n';
  }
  return 0;
}
