#include <bits/stdc++.h>
using namespace std;
long long f[100];
long long d[100][2];
int q[100];
int main() {
  f[1] = 1;
  f[2] = 2;
  for (int i = 3; i < 90; ++i) f[i] = f[i - 1] + f[i - 2];
  int tt;
  scanf("%d", &tt);
  while (tt--) {
    long long n;
    int m = 0;
    scanf("%I64d", &n);
    for (int i = 89; i > 0; --i) {
      if (n >= f[i]) {
        q[++m] = i;
        n -= f[i];
      }
    }
    reverse(q + 1, q + 1 + m);
    d[1][0] = 1;
    d[1][1] = (q[1] - 1) / 2;
    for (int i = 2; i <= m; ++i) {
      d[i][0] = d[i - 1][0] + d[i - 1][1];
      d[i][1] = (q[i] - q[i - 1] - 1) / 2 * d[i - 1][0] +
                (q[i] - q[i - 1]) / 2 * d[i - 1][1];
    }
    printf("%I64d\n", d[m][0] + d[m][1]);
  }
}
