#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
const double eps = 1e-9;
long long F[100];
long long loo = 2000000000000000000LL;
int mark[100];
int num[100];
int K;
int dp[100][2];
int rek(int n, int k) {
  if (n == K) return 1 - k;
  if (dp[n][k] == -1) {
    int st = 0;
    st = num[n] / 2 + 1;
    if (k) st--;
    dp[n][k] = st * rek(n + 1, 0);
    if (num[n] & 1) dp[n][k] += rek(n + 1, 1);
  }
  return dp[n][k];
}
int main() {
  F[0] = 1;
  F[1] = 2;
  for (int i = (2); i < (100); i++) F[i] = min(F[i - 1] + F[i - 2], loo);
  int tc;
  cin >> tc;
  while (tc--) {
    long long cur;
    cin >> cur;
    long long kk = cur;
    for (int i = int(87) - 1; i >= (0); i--) {
      if (kk >= F[i]) {
        mark[i] = 1;
        kk -= F[i];
      } else {
        mark[i] = 0;
      }
    }
    K = 0;
    int id = 86;
    while (mark[id] == 0) --id;
    while (id >= 0) {
      --id;
      num[K] = 0;
      while (id >= 0 && mark[id] == 0) {
        num[K]++;
        --id;
      }
      ++K;
    }
    memset(dp, -1, sizeof(dp));
    cout << rek(0, 0) << endl;
  }
  return 0;
}
