#include <bits/stdc++.h>
using namespace std;
long long a[105], b;
int c, d, e, f[105][2], g, h, i, j, k, l, m, n, v[105];
int main() {
  a[1] = 1;
  a[2] = 2;
  for (n = 3;; n++) {
    a[n] = a[n - 1] + a[n - 2];
    if (a[n] > 1e18) break;
  }
  int t = 0;
  scanf("%d", &t);
  for (; t; t--) {
    scanf("%I64d", &b);
    for (i = n, g = 0; i; i--)
      if (b >= a[i]) {
        b -= a[i];
        v[++g] = i;
      }
    for (i = 1; i + i <= g; i++) swap(v[i], v[g - i + 1]);
    memset(f, 0, sizeof(f));
    f[1][0] = 1;
    f[1][1] = (v[1] - 1) / 2;
    for (i = 2; i <= g; i++) {
      f[i][0] = f[i - 1][0] + f[i - 1][1];
      f[i][1] = (v[i] - v[i - 1] - 1) / 2 * f[i - 1][0] +
                (v[i] - v[i - 1]) / 2 * f[i - 1][1];
    }
    printf("%d\n", f[g][0] + f[g][1]);
  }
  return 0;
}
