#include <bits/stdc++.h>
using namespace std;
long long fib[100];
bool vis[100];
long long sum[2][2];
int main() {
  fib[0] = fib[1] = 1;
  for (int i = 2; fib[i - 1] <= (long long)1e18; ++i) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  int test;
  scanf("%d", &test);
  while (test--) {
    long long n;
    cin >> n;
    memset(vis, 0, sizeof(vis));
    for (int i = 87; i >= 0; --i) {
      if (n >= fib[i]) {
        n -= fib[i];
        vis[i] = 1;
      }
    }
    int now(1), pre(0);
    sum[0][0] = 1;
    sum[0][1] = 0;
    for (int i = 1; i <= 87; ++i) {
      if (vis[i]) {
        sum[now][0] = sum[!now][0] + sum[!now][1];
        sum[now][1] = (long long)(i - pre - 1) / 2 * sum[!now][0] +
                      (long long)(i - pre) / 2 * sum[!now][1];
        now = !now;
        pre = i;
      }
    }
    cout << sum[!now][0] + sum[!now][1] << endl;
  }
  return 0;
}
