#include <bits/stdc++.h>
using namespace std;
void solve() {
  long long int a = 0, b = 1, count = 2;
  vector<long long int> A;
  A.push_back(a);
  A.push_back(b);
  while (b < 1e18) {
    long long int u = a + b;
    A.push_back(a + b);
    count++;
    a = b;
    b = u;
  }
  long long int sum;
  cin >> sum;
  int y = A.size();
  vector<long long int> lol;
  for (int i = y - 1; i > 1; i--) {
    if (sum >= A[i]) {
      sum -= A[i];
      lol.push_back(i);
      i--;
    }
    if (sum == 0) {
      break;
    }
  }
  lol.push_back(1);
  reverse(lol.begin(), lol.end());
  long long int dp[2][91] = {0};
  dp[0][0] = 1;
  for (int i = 1; i < lol.size(); i++) {
    long long int u = (lol[i] - lol[i - 1] - 1);
    dp[0][i] = dp[0][i - 1] + dp[1][i - 1];
    dp[1][i] = (u / 2) * dp[0][i - 1] + ((u + 1) / 2) * dp[1][i - 1];
  }
  cout << dp[0][lol.size() - 1] + dp[1][lol.size() - 1] << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) solve();
}
