#include <bits/stdc++.h>
using namespace std;
int n;
long long fib[88];
long long x;
int y;
vector<char> z;
vector<long long> ans[2];
int main() {
  fib[0] = 1;
  fib[1] = 2;
  for (int a = 2; a < 88; a++) fib[a] = fib[a - 1] + fib[a - 2];
  scanf("%d", &n);
  while (n-- > 0) {
    scanf("%I64d", &x);
    y = 0;
    while (fib[y + 1] <= x) y++;
    z.clear();
    while (x) {
      if (fib[y] <= x) {
        x -= fib[y];
        z.push_back(y);
      }
      y--;
    }
    z.push_back(-1);
    ans[0].clear();
    ans[1].clear();
    ans[0].push_back(1);
    ans[1].push_back(0);
    for (int a = z.size() - 2; a >= 0; a--) {
      ans[0].push_back(ans[0].back() + ans[1].back());
      ans[1].push_back((z[a] - z[a + 1] + 1) / 2 * ans[0][ans[0].size() - 2] +
                       (z[a] - z[a + 1] + 2) / 2 * ans[1].back() -
                       ans[0].back());
    }
    printf("%I64d\n", ans[0].back() + ans[1].back());
  }
  return 0;
}
