#include <bits/stdc++.h>
using namespace std;
const long long maxN = 1e2 + 13;
long long t, f[maxN], dp1[maxN], dp2[maxN];
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> t;
  f[1] = 1;
  f[2] = 2;
  for (long long i = 3; i <= 90; i++) {
    f[i] = f[i - 1] + f[i - 2];
  }
  while (t--) {
    long long n;
    cin >> n;
    vector<long long> vec;
    vec.clear();
    for (long long i = 90; i >= 1; i--)
      if (n >= f[i]) {
        n -= f[i];
        vec.push_back(i);
      }
    memset(dp1, 0, sizeof dp1);
    memset(dp2, 0, sizeof dp2);
    vec.push_back(0);
    dp1[vec.size() - 1] = 1;
    for (long long i = vec.size() - 2; i >= 0; i--) {
      dp1[i] = dp2[i + 1] + dp1[i + 1];
      dp2[i] = dp1[i + 1] * ((vec[i] - vec[i + 1] - 1) / 2) +
               dp2[i + 1] * ((vec[i] - vec[i + 1]) / 2);
    }
    cout << dp1[0] + dp2[0] << '\n';
  }
}
