#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
const long long MXN = 3e5 + 10;
const long long MXK = 89;
long long q, n;
long long fib[MXK], dp[3][MXK];
bool rep[MXK];
void solve() {
  cin >> n;
  for (int i = MXK - 1; i; i--) {
    rep[i] = dp[0][i] = dp[1][i] = dp[2][i] = 0;
    if (n >= fib[i]) rep[i] = 1, n -= fib[i];
  }
  dp[0][0] = 1;
  for (int i = 1; i < MXK; i++) {
    if (rep[i]) {
      dp[0][i] = dp[0][i - 1] + dp[2][i - 1];
      dp[1][i] = dp[2][i - 1];
    } else {
      dp[0][i] = dp[0][i - 1];
      dp[1][i] = dp[0][i - 1] + dp[2][i - 1];
      dp[2][i] = dp[1][i - 1];
    }
  }
  cout << dp[0][MXK - 1] << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  fib[1] = 1, fib[2] = 2;
  for (int i = 3; i < MXK; i++) fib[i] = fib[i - 1] + fib[i - 2];
  cin >> q;
  while (q--) solve();
  return 0;
}
