#include <bits/stdc++.h>
using namespace std;
const long long M = 1000000000000000000LL;
long long f[102];
int dp[102][102], size, a[102];
void init() {
  f[0] = 1;
  f[1] = 1;
  for (size = 2; f[size - 2] + f[size - 1] <= M; ++size)
    f[size] = f[size - 1] + f[size - 2];
}
int main() {
  int t;
  init();
  cin >> t;
  while (t--) {
    long long x;
    scanf("%I64d", &x);
    int i = size;
    while (--i) {
      if (x >= f[i]) {
        x -= f[i];
        a[i] = 1;
      } else
        a[i] = 0;
    }
    int k = 0;
    dp[0][0] = 0;
    dp[0][1] = 1;
    for (int i = 1; i < size; ++i)
      if (a[i] == 1) {
        dp[i][0] = dp[k][1] * ((i - k - 1) / 2) + dp[k][0] * ((i - k) / 2);
        dp[i][1] = dp[k][1] + dp[k][0];
        k = i;
      }
    printf("%d\n", dp[k][0] + dp[k][1]);
  }
  return 0;
}
