#include <bits/stdc++.h>
using namespace std;
bool mark[123];
long long t, n;
long long f[123], dp[123][3][3];
int main() {
  f[1] = 1;
  f[2] = 2;
  for (int i = 3; i <= 87; i++) f[i] = f[i - 1] + f[i - 2];
  cin >> t;
  for (int o = 1; o <= t; o++) {
    cin >> n;
    memset(mark, false, sizeof mark);
    for (int i = 87; i; i--)
      if (f[i] <= n) {
        mark[i] = true;
        n -= f[i];
      }
    for (int x = 0; x < 2; x++)
      for (int y = 0; y < 2; y++) dp[1][x][y] = 0;
    if (mark[1])
      dp[1][0][0] = 1;
    else
      dp[1][0][0] = dp[1][1][0] = 1;
    for (int i = 2; i <= 88; i++) {
      for (int x = 0; x < 3; x++)
        for (int y = 0; y < 3; y++) {
          dp[i][x][y] = 0;
          int xx = x + mark[i];
          if (xx >= 3) continue;
          if (xx + y < 3) dp[i][x][y] += dp[i - 1][xx + y][xx];
          if (xx != 0 && (xx - 1 + y) < 3)
            dp[i][x][y] += dp[i - 1][xx - 1 + y][xx - 1];
        }
    }
    cout << dp[88][0][0] << endl;
  }
  return 0;
}
