#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100 + 10;
constexpr int LG = 20;
constexpr int MOD = 1e9 + 7;
constexpr int MOD2 = 1e9 + 9;
long long n, t, dp[N][2], F[N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> t;
  F[1] = 1;
  F[2] = 2;
  for (int i = 3;; i++) {
    F[i] = F[i - 1] + F[i - 2];
    if (F[i] > 1e18) break;
  }
  while (t--) {
    cin >> n;
    memset(dp, 0, sizeof(dp));
    vector<int> v;
    for (int i = 87; i; i--) {
      if (n >= F[i]) {
        n -= F[i];
        v.push_back(i);
      }
    }
    v.push_back(0);
    dp[(int)v.size() - 1][0] = 1;
    for (int i = (int)v.size() - 2; ~i; i--) {
      dp[i][0] = dp[i + 1][0] + dp[i + 1][1];
      dp[i][1] = ((v[i] - v[i + 1] - 1) / 2) * dp[i + 1][0] +
                 ((v[i] - v[i + 1]) / 2) * dp[i + 1][1];
    }
    cout << dp[0][0] + dp[0][1] << '\n';
  }
  return 0;
}
