#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long f[110], dp[110][2];
int seq[110];
int main() {
  int t;
  long long n;
  cin >> t;
  f[1] = 1;
  f[2] = 2;
  for (int i = 3; i < 89; ++i) {
    f[i] = f[i - 1] + f[i - 2];
  }
  while (t--) {
    memset(seq, 0, sizeof(seq));
    scanf("%lld", &n);
    int k = 88, m = 0;
    while (n) {
      if (n >= f[k]) {
        n -= f[k];
        seq[m++] += k;
      }
      k--;
    }
    sort(seq, seq + m);
    dp[0][0] = 1;
    dp[0][1] = (seq[0] - 1) / 2;
    for (int i = 1; i < m; ++i) {
      dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
      dp[i][1] = dp[i - 1][0] * ((seq[i] - seq[i - 1] - 1) / 2) +
                 dp[i - 1][1] * ((seq[i] - seq[i - 1]) / 2);
    }
    printf("%lld\n", dp[m - 1][0] + dp[m - 1][1]);
  }
  return 0;
}
