#include <bits/stdc++.h>
using namespace std;
void ASS(bool b) {
  if (!b) {
    ++*(int*)0;
  }
}
#pragma comment(linker, "/STACK:106777216")
long long f[200];
char s[128];
long long read() {
  long long res = 0;
  scanf("%s", s);
  for (int i = 0; s[i]; i++) res = res * 10 + s[i] - '0';
  return res;
}
void write(long long x) {
  ASS(x > 0);
  int p = 0;
  while (x) {
    s[p++] = '0' + x % 10;
    x /= 10;
  }
  s[p] = 0;
  reverse(s, s + p);
  printf("%s\n", s);
}
long long dp[90][2][2];
long long Solve(long long n) {
  int pos = 87;
  while (f[pos] > n) pos--;
  int k = 0;
  while (pos >= 0) {
    if (f[pos] <= n) {
      n -= f[pos];
      s[k] = 1;
    } else
      s[k] = 0;
    pos--;
    k++;
  }
  ASS(n == 0);
  memset(dp, 0, sizeof(dp));
  dp[0][0][0] = 1;
  for (int i = 0; i < (int)(k); i++) {
    if (s[i]) {
      dp[i + 1][0][0] = dp[i][0][0];
      dp[i + 1][1][1] = dp[i][0][0];
    } else {
      dp[i + 1][0][0] = dp[i][0][0];
    }
    if (s[i]) {
      dp[i + 1][1][1] += dp[i][0][1];
    } else {
      dp[i + 1][0][0] += dp[i][0][1];
      dp[i + 1][1][1] += dp[i][0][1];
    }
    if (s[i]) {
      dp[i + 1][0][1] += dp[i][1][0];
    } else {
      dp[i + 1][0][1] += dp[i][1][0];
    }
    if (s[i]) {
    } else {
      dp[i + 1][0][1] += dp[i][1][1];
    }
  }
  return dp[k][0][0];
}
int main() {
  f[0] = 1;
  f[1] = 2;
  for (int i = 2; i <= 87; i++) f[i] = f[i - 1] + f[i - 2];
  int n;
  scanf("%d", &n);
  for (int i = 0; i < (int)(n); i++) {
    long long x = read();
    x = Solve(x);
    write(x);
  }
  return 0;
}
