#include <bits/stdc++.h>
using namespace std;
long long a[89];
int v[89];
int main() {
  int i, j, t;
  long long n;
  a[0] = 1, a[1] = 1;
  for (i = 2; i < 89; i++) a[i] = a[i - 1] + a[i - 2];
  scanf("%d", &t);
  while (t--) {
    scanf("%I64d", &n);
    memset(v, 0, sizeof(v));
    for (i = 89 - 1; i > 0; i--)
      if (n >= a[i]) v[i] = 1, n -= a[i];
    int last = 0;
    if (v[1]) last = 1;
    if (v[2]) last = 2;
    long long b = 1, c = 0;
    for (i = 3; i < 89; i++)
      if (v[i]) {
        long long bb = b + c, cc;
        cc = (i - last - 1) / 2 * b + (i - last) / 2 * c;
        b = bb, c = cc;
        last = i;
      }
    printf("%I64d\n", b + c);
  }
  return 0;
}
