#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
vector<int> V;
long long fib[MAXN];
long long n;
long long dp[MAXN][2];
int main(void) {
  fib[0] = 1;
  fib[1] = 1;
  for (int i = 2; i < MAXN; ++i) fib[i] = fib[i - 1] + fib[i - 2];
  int t;
  scanf("%d", &t);
  while (t--) {
    V.clear();
    scanf("%lld", &n);
    int t = 0;
    while (fib[t++] < n)
      ;
    for (int i = t; i >= 1; --i)
      if (fib[i] <= n) {
        V.push_back(i);
        n -= fib[i];
      }
    V.push_back(0);
    sort(V.begin(), V.end());
    dp[0][0] = 1;
    dp[0][1] = 0;
    for (int i = 1; i < V.size(); ++i) {
      dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
      dp[i][1] = dp[i - 1][0] * ((V[i] - V[i - 1] - 1) / 2) +
                 dp[i - 1][1] * ((V[i] - V[i - 1]) / 2);
    }
    printf("%lld\n", dp[(int)V.size() - 1][0] + dp[(int)V.size() - 1][1]);
  }
  return 0;
}
