#include <bits/stdc++.h>
using namespace std;
long long dp[87];
long long check[87];
pair<int, int> dap[2];
int main() {
  dp[1] = 1;
  dp[2] = 2;
  for (int i = 3; i <= 86; i++) dp[i] = dp[i - 1] + dp[i - 2];
  long long t;
  scanf("%lld", &t);
  while (t--) {
    dap[0] = {0, 1};
    dap[1] = {0, 0};
    long long n;
    scanf("%lld", &n);
    for (int i = 86; i >= 1; i--) {
      if (dp[i] <= n) {
        check[i] = 1;
        n -= dp[i];
      } else
        check[i] = 0;
    }
    for (int i = 1; i <= 86; i++) {
      if (check[i]) {
        int gap = dap[0].second + dap[1].second;
        int g = (i - dap[0].first - 1) / 2;
        int xx = g * dap[0].second;
        g = (i - dap[1].first - 1) / 2;
        xx += g * dap[1].second;
        dap[0] = {i, gap};
        dap[1] = {i - 1, xx};
      }
    }
    printf("%d\n", dap[0].second + dap[1].second);
  }
}
