#include <bits/stdc++.h>
using namespace std;
int dp[100][2];
long long int fi[100];
void init() {
  fi[1] = fi[2] = 1;
  for (int i = 3; i <= 88; i++) fi[i] = fi[i - 1] + fi[i - 2];
}
int main() {
  int T;
  cin >> T;
  init();
  while (T--) {
    long long int n;
    cin >> n;
    int id[100];
    int cnt = 0;
    for (int i = 88; i >= 1; i--) {
      if (n >= fi[i]) {
        n = n - fi[i];
        id[++cnt] = i;
      }
    }
    sort(id + 1, id + cnt + 1);
    dp[1][0] = (id[1] - 2) / 2;
    dp[1][1] = 1;
    for (int i = 2; i <= cnt; i++) {
      dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
      dp[i][0] = dp[i - 1][1] * ((id[i] - id[i - 1] - 1) / 2) +
                 dp[i - 1][0] * ((id[i] - id[i - 1]) / 2);
    }
    cout << dp[cnt][0] + dp[cnt][1] << endl;
  }
}
