#include <bits/stdc++.h>
using namespace std;
long long fibo[90];
bool mask[90];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  fibo[0] = 1ll, fibo[1] = 1ll;
  for (int i = 2; i <= 86; i++) fibo[i] = fibo[i - 1] + fibo[i - 2];
  int t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    memset(mask, false, sizeof(mask));
    for (int i = 86; i > 0; i--)
      if (n >= fibo[i]) n -= fibo[i], mask[i] = true;
    long long dp1 = 1ll, dp2 = 0ll, cnt = 0ll;
    for (int i = 1; i <= 86; i++)
      if (mask[i]) {
        long long dp1nx = dp1 + dp2;
        long long dp2nx = dp1 * ((i - cnt - 1) / 2) + dp2 * ((i - cnt) / 2);
        dp1 = dp1nx;
        dp2 = dp2nx;
        cnt = i;
      }
    cout << dp1 + dp2 << endl;
  }
  return 0;
}
