#include <bits/stdc++.h>
using namespace std;
long long F[88];
void pre() {
  F[1] = 1, F[2] = 2;
  for (int i = 3; i <= 87; ++i) F[i] = F[i - 1] + F[i - 2];
}
long long dp[88][2];
int W[88];
int main() {
  pre();
  int t, tot, p;
  for (scanf("%d", &t); t--;) {
    long long n;
    scanf("%I64d", &n);
    for (tot = 87, p = 0; n; --tot)
      if (n >= F[tot]) n -= F[tot], W[p++] = tot;
    memset(dp, 0, sizeof(dp));
    dp[p - 1][0] = 1, dp[p - 1][1] = (W[p - 1] - 1) / 2;
    for (int i = p - 2; i >= 0; --i) {
      dp[i][0] = dp[i + 1][1] + dp[i + 1][0];
      if (W[i] - W[i + 1] - 1 >= 2)
        dp[i][1] += (W[i] - W[i + 1] - 1) / 2 * dp[i + 1][0];
      if (W[i] - W[i + 1] - 1 >= 1 && dp[i + 1][1])
        dp[i][1] += (W[i] - W[i + 1]) / 2 * dp[i + 1][1];
    }
    printf("%I64d\n", dp[0][0] + dp[0][1]);
  }
}
