#include <bits/stdc++.h>
using namespace std;
int main() {
  long long a[86], n;
  int T, m, b[86], x, y, xx, yy, tmp;
  a[0] = 1;
  a[1] = 2;
  for (int i = 2; i < 86; ++i) a[i] = a[i - 2] + a[i - 1];
  scanf("%d", &T);
  for (int t = 0; t < T; ++t) {
    scanf("%I64d", &n);
    m = 0;
    for (int i = 85; i >= 0 && n != 0; --i)
      if (n >= a[i]) {
        b[m++] = i;
        n -= a[i];
      }
    x = b[m - 1] / 2;
    y = x + 1;
    for (int i = m - 2; i >= 0; --i) {
      tmp = (b[i] - b[i + 1] - 1) / 2;
      xx = y * tmp;
      yy = y * (tmp + 1);
      if ((b[i] - b[i + 1]) % 2 == 0) {
        y = x + yy;
        x += xx;
      } else {
        x = xx;
        y = yy;
      }
    }
    printf("%d\n", y);
  }
  return 0;
}
