#include <bits/stdc++.h>
using namespace std;
long long F[100];
int zero[100];
long long dp[100][2];
int main() {
  F[1] = 1;
  F[2] = 2;
  int q = 2;
  while (F[q] < 1000000000000000000LL) {
    F[q + 1] = F[q] + F[q - 1];
    ++q;
  }
  int t;
  cin >> t;
  for (int i = 0; i < t; ++i) {
    long long n;
    cin >> n;
    memset(zero, 0, sizeof zero);
    int tot = 0, qq = 0;
    bool was = false;
    for (int j = q; j > 0; --j) {
      if (n >= F[j]) {
        n -= F[j];
        if (was) {
          zero[tot++] = qq;
        }
        was = true;
        qq = -1;
      }
      ++qq;
    }
    zero[tot++] = qq;
    reverse(zero, zero + tot);
    long long ret = 0;
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for (int j = 0; j < tot; j++) {
      dp[j + 1][0] += dp[j][0] + dp[j][1];
      dp[j + 1][1] += (zero[j] / 2) * dp[j][0] + (zero[j] + 1) / 2 * dp[j][1];
    }
    ret = dp[tot][0] + dp[tot][1];
    cout << ret << endl;
  }
  return 0;
}
