#include <bits/stdc++.h>
using namespace std;
int main() {
  long long n, x[90] = {1, 1}, f[90][2];
  for (register int i = 2; i < 89; ++i) x[i] = x[i - 1] + x[i - 2];
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%I64d", &n);
    int a[90], cnt = 0;
    for (register int i = 88; i; --i)
      if (x[i] <= n) n -= x[i], a[++cnt] = i;
    reverse(a + 1, a + cnt + 1);
    f[1][1] = 1, f[1][0] = (a[1] - 1) / 2;
    for (int i = 2; i <= cnt; i++) {
      f[i][1] = f[i - 1][0] + f[i - 1][1];
      f[i][0] = (a[i] - a[i - 1]) / 2 * f[i - 1][0] +
                (a[i] - a[i - 1] - 1) / 2 * f[i - 1][1];
    }
    printf("%I64d\n", f[cnt][0] + f[cnt][1]);
  }
  return 0;
}
