#include <bits/stdc++.h>
using namespace std;
long long f[100];
int a[100];
int n;
long long ans, x;
void rec(int x, int y, int k) {
  if (x == 0) {
    for (int i = 0; i < 10; ++i)
      if (a[i]) printf("%i + ", f[i]);
    printf("=%i\n", y);
  } else {
    for (int i = k; i >= 0; --i)
      if (f[i] <= x) {
        a[i] = 1;
        rec(x - f[i], y, i - 1);
        a[i] = 0;
      }
  }
}
int main() {
  n = 86;
  f[0] = 1;
  f[1] = 2;
  x = 1;
  for (int i = 1; i <= 18; ++i) x *= 10;
  for (int i = 2; i < n; ++i) {
    f[i] = f[i - 1] + f[i - 2];
  }
  int tc, tt;
  scanf("%i", &tc);
  for (tt = 1; tt <= tc; ++tt) {
    scanf("%I64d", &x);
    for (int i = 0; i < n; ++i) a[i] = 0;
    for (int i = n - 1; i >= 0; --i)
      if (f[i] <= x) {
        a[i] = 1;
        x -= f[i];
      }
    ans = 1;
    for (int i = 0; i < n; ++i)
      if (a[i]) {
        long long f0 = 1;
        long long f1 = i / 2;
        long long nf0, nf1;
        int p = i;
        for (int j = i + 1; j < n; ++j)
          if (a[j]) {
            nf0 = f0 + f1;
            nf1 = f1 * ((j - p) / 2) + f0 * ((j - p - 1) / 2);
            f0 = nf0;
            f1 = nf1;
            p = j;
          }
        ans = f0 + f1;
        break;
      }
    printf("%I64d\n", ans);
  }
  return 0;
}
