#include <bits/stdc++.h>
using namespace std;
const long long INF = (long long)(1e18);
int t, s;
long long n;
long long fib[100];
int a[100], m;
long long dp[100][2];
int main() {
  fib[0] = 1;
  fib[1] = 2;
  for (int i = 2; i < 100; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
    if (fib[i] >= INF) {
      s = i;
      break;
    }
  }
  cin >> t;
  while (t--) {
    cin >> n;
    m = 0;
    for (int i = s - 1; i >= 0; i--)
      if (n >= fib[i]) {
        a[m++] = i;
        n -= fib[i];
      }
    dp[m - 1][0] = a[m - 1] / 2;
    dp[m - 1][1] = 1;
    for (int i = m - 2; i >= 0; i--) {
      int t = a[i] - a[i + 1];
      dp[i][0] = t / 2 * dp[i + 1][0] + (t - 1) / 2 * dp[i + 1][1];
      dp[i][1] = dp[i + 1][0] + dp[i + 1][1];
    }
    cout << dp[0][0] + dp[0][1] << endl;
  }
  return 0;
}
