#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
const int Max = 1000;
int main() {
  vector<long long> fibs;
  fibs.push_back(0);
  fibs.push_back(1);
  fibs.push_back(2);
  for (int i = 3; i <= 87; i++) {
    fibs.push_back(fibs[i - 1] + fibs[i - 2]);
  }
  int t;
  cin >> t;
  for (int T = 0; T < t; T++) {
    long long n;
    cin >> n;
    vector<int> s;
    long long num = n;
    int ind = 87;
    int cnt = 0;
    while (num > 0 && ind > 0) {
      if (fibs[ind] <= num) {
        num -= fibs[ind];
        s.push_back(ind);
        cnt++;
      }
      ind--;
    }
    s.push_back(0);
    sort(s.begin(), s.end());
    long long dp[cnt + 1][2];
    dp[0][0] = 1;
    dp[0][1] = 0;
    for (int i = 1; i <= cnt; i++) {
      dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
      dp[i][1] = dp[i - 1][0] * ((s[i] - s[i - 1] - 1) / 2) +
                 dp[i - 1][1] * ((s[i] - s[i - 1]) / 2);
    }
    cout << dp[cnt][0] + dp[cnt][1] << endl;
  }
}
