#include <bits/stdc++.h>
using namespace std;
int nq;
int b[100];
long long n, ans;
long long a[100], f[100][2];
int main() {
  int i, j, q;
  long long t;
  a[0] = 1;
  a[1] = 1;
  for (i = 2; i <= 88; i++) a[i] = a[i - 1] + a[i - 2];
  scanf("%d", &nq);
  for (q = 1; q <= nq; q++) {
    scanf("%I64d", &n);
    t = n;
    memset(b, 0, sizeof(b));
    for (j = 88; j >= 1; j--)
      if (t >= a[j]) {
        b[j] = 1;
        t -= a[j];
      }
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    j = 0;
    for (i = 1; i <= 88; i++)
      if (b[i] == 1) {
        f[i][0] = f[j][0] + f[j][1];
        f[i][1] = f[j][0] * ((i - j - 1) / 2) + f[j][1] * ((i - j) / 2);
        j = i;
      }
    ans = f[j][0] + f[j][1];
    printf("%I64d\n", ans);
  }
  return 0;
}
