#include <bits/stdc++.h>
using namespace std;
const int max_N = 100 + 10;
long long f[max_N], dp[max_N][2];
int z[max_N];
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  f[0] = 1, f[1] = 2;
  for (int i = 2; i < 88; i++) f[i] = f[i - 1] + f[i - 2];
  int t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    string s = "";
    int p(87), m(0), q;
    while (p >= 0) {
      if (f[p] <= n) {
        s += '1';
        m++;
        n -= f[p];
      } else if (m)
        s += '0';
      p--;
    }
    p = -1, q = 0;
    fill(z, z + m + 1, 0);
    while (q < (int)s.size()) {
      if (s[q] == '1')
        p++;
      else
        z[p]++;
      q++;
    }
    dp[m][0] = 0, dp[m][1] = 1;
    for (int i = m - 1; i >= 0; i--) {
      dp[i][0] =
          (dp[i + 1][0] * ((z[i] + 1) / 2)) + (dp[i + 1][1] * (z[i] / 2));
      dp[i][1] = dp[i + 1][0] + dp[i + 1][1];
    }
    cout << dp[0][0] + dp[0][1] << "\n";
  }
  return 0;
}
