#include <bits/stdc++.h>
using namespace std;
long long F[100];
long long dp1[100], dp2[100];
int main() {
  F[0] = 1;
  F[1] = 2;
  for (int i = 2; i < 100; ++i) F[i] = F[i - 1] + F[i - 2];
  int cas;
  cin >> cas;
  while (cas--) {
    long long n;
    cin >> n;
    vector<long long> a;
    for (int i = 86; n > 0; --i) {
      if (F[i] <= n) {
        n -= F[i];
        a.push_back(i);
      }
    }
    reverse(a.begin(), a.end());
    int k = (int)(a.size());
    dp1[0] = 1;
    dp2[0] = a[0] / 2;
    for (int i = 1; i < k; ++i) {
      dp1[i] = dp1[i - 1] + dp2[i - 1];
      dp2[i] = (a[i] - a[i - 1] - 1) / 2 * dp1[i - 1] +
               (a[i] - a[i - 1]) / 2 * dp2[i - 1];
    }
    cout << dp1[k - 1] + dp2[k - 1] << endl;
  }
  return 0;
}
