#include <bits/stdc++.h>
using namespace std;
long long int fib[100];
long long int dp[100][4];
long long int used[100];
bool decode(long long int num, long long int pos) {
  if (num == 0) return true;
  if (pos < 0) return false;
  if (fib[pos] <= num) used[pos] = 1;
  if (fib[pos] <= num) num -= fib[pos];
  return decode(num, pos - 1);
}
long long int recur(long long int pos, long long int mask) {
  long long int &res = dp[pos][mask];
  if (res != -1) return res;
  if (mask == 1 && used[pos]) {
    return res = recur(pos - 1, 3);
  }
  if (mask == 3 && used[pos]) return res = 0;
  if (pos == 0) return res = 1 - mask / 2;
  mask |= used[pos];
  res = recur(pos - 1, mask / 2);
  if (mask == 1) res = res + recur(pos - 1, 3);
  return res;
}
int main() {
  fib[0] = 1;
  fib[1] = 2;
  for (long long int i = 0; i < ((long long int)(100)); ++i)
    if (2 <= i) fib[i] = fib[i - 1] + fib[i - 2];
  long long int maxi = 100 - 1;
  for (long long int i = 100 - 1; 0 <= i; i--)
    if (fib[i] < 0) maxi = i - 1;
  long long int n;
  cin >> n;
  for (long long int i = 0; i < ((long long int)(n)); ++i) {
    long long int num;
    cin >> num;
    memset(used, 0, sizeof(used));
    memset(dp, -1, sizeof(dp));
    if (!decode(num, maxi)) {
      cout << 0 << endl;
      continue;
    }
    cout << recur(maxi, 0) << endl;
  }
}
