#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:64000000")
using namespace std;
long long f[87];
long long d[87][2];
int a[87];
void solve() {
  long long x;
  cin >> x;
  memset(a, 0, sizeof(a));
  for (int i = 87 - 1; i >= 0; i--) {
    if (x >= f[i]) {
      x -= f[i];
      a[i]++;
    }
  }
  memset(d, 0, sizeof(d));
  d[0][0] = 1;
  if (a[0] == 0) d[0][1] = 1;
  d[1][0] = 1;
  if (a[1] == 0) d[1][1] = 1;
  for (int i = 2; i < 87; i++) {
    if (a[i] == 0) {
      d[i][0] = d[i - 1][0];
      d[i][1] = d[i - 1][0];
      if (a[i - 1] == 0) {
        d[i][1] += d[i - 2][1];
      }
    } else {
      d[i][0] = d[i - 1][0] + d[i - 2][1];
      d[i][1] = d[i - 2][1];
    }
  }
  cout << d[87 - 1][0] << endl;
}
int main() {
  f[0] = 1;
  f[1] = 2;
  for (int i = 2; i < 87; i++) {
    f[i] = f[i - 1] + f[i - 2];
  }
  int tc;
  cin >> tc;
  for (int it = 0; it < int(tc); it++) solve();
  return 0;
}
