#include <bits/stdc++.h>
using namespace std;
vector<long long> fib;
vector<int> v;
long long f[100][2];
int main() {
  fib.push_back(1);
  fib.push_back(1);
  while (true) {
    long long a = fib.back() + fib[fib.size() - 2];
    if (a > 1e18) break;
    fib.push_back(a);
  }
  int test;
  scanf("%d", &test);
  for (int cas = 1; cas <= test; ++cas) {
    long long n;
    scanf("%I64d", &n);
    v.clear();
    for (int i = fib.size() - 1; i > 0; --i)
      if (n >= fib[i]) {
        v.push_back(i);
        n -= fib[i];
      }
    v.push_back(0);
    reverse(v.begin(), v.end());
    f[0][1] = 1;
    f[0][0] = 0;
    int k = v.size() - 1;
    for (int i = 1; i <= k; ++i) {
      f[i][1] = f[i - 1][1] + f[i - 1][0];
      f[i][0] = (v[i] - v[i - 1] - 1) / 2 * f[i - 1][1] +
                (v[i] - v[i - 1]) / 2 * f[i - 1][0];
    }
    printf("%I64d\n", f[k][1] + f[k][0]);
  }
  return 0;
}
