#include <bits/stdc++.h>
using namespace std;
vector<long long> fibo(90);
void pre() {
  int k = 0;
  fibo[1] = 1;
  fibo[2] = 2;
  for (int i = 3; i < 90; i++) {
    fibo[i] = fibo[i - 1] + fibo[i - 2];
  }
}
int main() {
  int t;
  pre();
  cin >> t;
  for (int i = 0; i < t; i++) {
    long long n;
    cin >> n;
    vector<int> v;
    for (int i = 89; i >= 1; i--) {
      if (n >= fibo[i]) {
        n -= fibo[i];
        v.push_back(i);
      }
    }
    v.push_back(0);
    int p = 1, q = 0;
    for (int i = v.size() - 1; i >= 1; i--) {
      int dif = v[i - 1] - v[i] - 1;
      int P = p + q;
      int Q = p * (dif / 2) + q * ((dif + 1) / 2);
      p = P;
      q = Q;
    }
    cout << p + q << endl;
  }
  return 0;
}
