#include <bits/stdc++.h>
using namespace std;
const long long MAX = 1000000000000000000LL;
long long fib[105], dp[105][3][3];
int N, n, ax[105];
void init() {
  fib[0] = fib[1] = 1;
  for (N = 2;; N++) {
    fib[N] = fib[N - 1] + fib[N - 2];
    if (fib[N] > MAX) break;
  }
}
void sol(long long x) {
  for (int i = N; i >= 0; i--) {
    if (x >= fib[i])
      x -= fib[i], ax[i] = 1;
    else
      ax[i] = 0;
  }
}
int main() {
  init();
  int T;
  scanf("%d", &T);
  while (T--) {
    long long x;
    scanf("%I64d", &x);
    sol(x);
    memset(dp, 0, sizeof(dp));
    dp[N][0][0] = 1;
    for (int i = N; i > 0; i--)
      for (int p = 0; p < 3; p++)
        for (int q = 0; q < 3; q++)
          if (dp[i][p][q]) {
            int j = q + ax[i];
            for (int x = max(j - 1, 0); x <= j; x++) {
              int np = x, nq = p + x;
              if (np < 3 && nq < 3) dp[i - 1][np][nq] += dp[i][p][q];
            }
          }
    printf("%I64d\n", dp[0][0][0]);
  }
  return 0;
}
