#include <bits/stdc++.h>
using namespace std;
const long long MN = 90;
long long fib[MN];
int32_t main() {
  fib[0] = 1, fib[1] = 2;
  for (long long i = 2; i < MN; i++) fib[i] = fib[i - 1] + fib[i - 2];
  long long q;
  cin >> q;
  while (q--) {
    long long a;
    cin >> a;
    bool hav[MN] = {};
    for (long long i = MN - 2; i >= 0; i--)
      if (a >= fib[i]) {
        a -= fib[i];
        hav[i + 1] = true;
      }
    long long dp00[MN] = {}, dp10[MN] = {}, dp01[MN] = {};
    dp00[0] = 1;
    for (long long i = 1; i < MN; i++) {
      if (hav[i]) {
        dp00[i] = dp00[i - 1] + dp01[i - 1];
        dp10[i] = dp01[i - 1];
        dp01[i] = 0;
      } else {
        dp00[i] = dp00[i - 1];
        dp10[i] = dp00[i - 1] + dp01[i - 1];
        dp01[i] = dp10[i - 1];
      }
    }
    cout << dp00[MN - 1] << endl;
  }
}
