#include <bits/stdc++.h>
int n, i, j, T, k, y[88], a, b, c, d;
long long F[88], t;
int main() {
  F[1] = 1;
  F[n = 2] = 2;
  for (; n < 87;) F[++n] = F[n - 1] + F[n - 2];
  for (std::cin >> T; T--;) {
    std::cin >> t;
    for (i = n; i; --i)
      if (y[i] = t >= F[i]) t -= F[i];
    a = 1;
    b = k = 0;
    for (i = 1; i <= n; ++i)
      if (y[i]) {
        c = a + b;
        d = a * (i - k - 1 >> 1) + b * (i - k >> 1);
        a = c, b = d, k = i;
      }
    std::cout << a + b << "\n";
  }
}
