#include <bits/stdc++.h>
int n;
long long fib[100];
void brute(int g) {
  int i, j, sum;
  int k = 19;
  int cnt[10000] = {};
  for (i = 0; i < 1 << k; i++) {
    sum = 0;
    for (j = 0; j < k; j++)
      if (i & 1 << j) sum += fib[j];
    if (sum < 10000) cnt[sum]++;
    if (sum == 8934) {
      for (j = 0; j < k; j++)
        if (i & 1 << j) printf("%lld + ", fib[j]);
      puts("= 8934");
    }
  }
  printf("%d\n", cnt[g]);
}
long long dp[98][4][4];
char g[98];
long long solve(int depth, int now, int next) {
  int i, j, k;
  long long res = 0;
  int a, b, c;
  if (depth == 1 && now == 1 && next == 1) return 1;
  if (depth == 1) return 0;
  if (dp[depth][now][next] >= 0) return dp[depth][now][next];
  a = g[depth] + (now - 1);
  b = g[depth - 1] + (next - 1);
  c = g[depth - 2];
  if (a == 0 || a == 1) {
    res += solve(depth - 1, next, 1);
  }
  if (a == 0 && b != -1) {
    res += solve(depth - 1, next - 1, 0);
  }
  if ((a == 1 || a == 2) && b != 2) {
    res += solve(depth - 1, next + 1, 2);
  }
  return dp[depth][now][next] = res;
}
int main() {
  int i, j, k, l, m, n;
  long long in, res;
  int size;
  fib[0] = 1;
  fib[1] = 2;
  for (i = 2; i < 100; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
    if (fib[i] > 4000000000000000000LL) {
      n = i;
      break;
    }
  }
  scanf("%d", &size);
  while (size--) {
    scanf("%I64d", &in);
    for (i = 0; i < n + 2; i++)
      for (j = 0; j < 4; j++)
        for (k = 0; k < 4; k++) dp[i][j][k] = -1;
    for (i = n - 1; i >= 0; i--) {
      g[i + 2] = 0;
      if (in >= fib[i]) in -= fib[i], g[i + 2]++;
    }
    g[0] = g[1] = 0;
    res = solve(n - 1, 1, 1);
    printf("%I64d\n", res);
  }
  return 0;
}
