#include <bits/stdc++.h>
using namespace std;
const int K = 86;
const int MX = 2;
long long f[K], dp[K][2 * MX + 1][2 * MX + 1];
bool now[K];
int main() {
  int n;
  cin >> n;
  f[0] = 1, f[1] = 2;
  for (int i = 2; i < K; i++) f[i] = f[i - 1] + f[i - 2];
  for (int l = 0; l <= 1; l++)
    for (int k = 0; k <= 1; k++) dp[1][k][l] = 1;
  for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;
    if (x == 1) {
      cout << 1 << endl;
      continue;
    }
    int mx = 0;
    for (int j = K - 1; j >= 0; j--)
      if (x >= f[j]) {
        now[j] = 1;
        x -= f[j];
        if (!mx) mx = j;
      } else
        now[j] = 0;
    for (int j = 2; j < K; j++)
      for (int l = 0; l <= MX; l++)
        for (int k = 0; k <= MX; k++) dp[j][k][l] = 0;
    for (int j = 2; j <= mx; j++)
      for (int k = 0; k <= MX; k++)
        for (int l = 0; l <= MX; l++) {
          if (k) dp[j][k][l] += dp[j - 1][l + 1][now[j - 2] + 1];
          if (k <= 1) dp[j][k][l] += dp[j - 1][l][now[j - 2]];
        }
    cout << dp[mx][1][0] << endl;
  }
  return 0;
}
