#include <bits/stdc++.h>
using namespace std;
void myassert(bool cond) {
  while (!cond)
    ;
}
int main() {
  vector<unsigned long long> fib = {1, 2, 3};
  while (fib.back() <= 1000000000000000000LL) {
    unsigned long long a = fib[fib.size() - 1];
    unsigned long long b = fib[fib.size() - 2];
    fib.push_back(a + b);
  }
  int t;
  cin >> t;
  while (t--) {
    unsigned long long n;
    cin >> n;
    int l = upper_bound(fib.begin(), fib.end(), n) - fib.begin() - 1;
    myassert(l >= 0 && l + 1 < fib.size());
    myassert(fib[l] <= n && fib[l + 1] > n);
    vector<int> bits(l + 1, 0);
    {
      unsigned long long m = n;
      for (int i = l; i >= 0; i--) {
        myassert(0 <= i && i < bits.size());
        if (m >= fib[i]) {
          bits[i] = 1;
          m -= fib[i];
        }
      }
      myassert(m == 0);
    }
    unsigned long long dp[100][3][3] = {};
    dp[l + 1][bits[l]][(l - 1 >= 0 ? bits[l - 1] : 0)] = 1;
    for (int i = l; i >= 0; i--) {
      for (int d1 = 0; d1 < (int)(3); ++d1)
        for (int d2 = 0; d2 < (int)(3); ++d2) {
          unsigned long long curr = dp[i + 1][d1][d2];
          if (curr == 0) continue;
          for (int cd = 0; cd < (int)(2); ++cd)
            if (d1 - cd >= 0) {
              int nd1 = d2 + d1 - cd;
              int nd2 = d1 - cd;
              if (i - 2 >= 0 && bits[i - 2]) nd2++;
              if (nd1 < 3 && nd2 < 3) {
                dp[i][nd1][nd2] += curr;
              }
            }
        }
    }
    unsigned long long ans = dp[0][0][0];
    cout << ans << endl;
  }
  return 0;
}
