#include <bits/stdc++.h>
using namespace std;
long long INF = 1000000000000000000ll;
long long fib[100];
int used[100];
long long dp[100][2];
long long r(int pos, int carry) {
  if (dp[pos][carry] != -1) return dp[pos][carry];
  long long res = 0;
  if ((carry) && (used[pos])) {
    if (pos < 2) return dp[pos][carry] = 0;
    if (used[pos - 1]) return dp[pos][carry] = 0;
    return dp[pos][carry] = r(pos - 2, 1);
  }
  if (pos == 0) return 1;
  if (((carry) || used[pos]) && (pos >= 2) && (used[pos - 1] == 0))
    res += r(pos - 2, 1);
  res += r(pos - 1, 0);
  return dp[pos][carry] = res;
}
int main() {
  fib[0] = 1;
  fib[1] = 2;
  int n = 2;
  while (1) {
    long long c = fib[n - 1] + fib[n - 2];
    if (c > INF) break;
    fib[n++] = c;
  }
  int t;
  scanf("%d", &t);
  while (t--) {
    long long num;
    scanf("%I64d", &num);
    memset(used, 0, sizeof(used));
    memset(dp, -1, sizeof(dp));
    for (int i = n - 1; i >= 0; --i) {
      if (num >= fib[i]) {
        used[i] = 1;
        num -= fib[i];
      }
    }
    memset(dp, -1, sizeof(dp));
    long long res = r(n - 1, 0);
    printf("%I64d\n", res);
  }
  return 0;
}
