#include <bits/stdc++.h>
const long long inf = (long long)2e18;
const int maxn = 200;
long long f[maxn];
int a[maxn];
long long dp[maxn][2];
int main() {
  int tt;
  scanf("%d", &tt);
  f[0] = 1, f[1] = 1;
  int fn = 2;
  for (int i = 2; f[i - 1] < inf; i++) {
    f[i] = f[i - 1] + f[i - 2];
    fn++;
  }
  while (tt--) {
    long long n;
    scanf("%I64d", &n);
    for (int i = fn - 1; i >= 0; i--) {
      if (n >= f[i]) {
        a[i - 1] = 1;
        n -= f[i];
      } else
        a[i - 1] = 0;
    }
    int k = 0;
    dp[0][0] = 0;
    dp[0][1] = 1;
    for (int i = 0; i < fn; i++)
      if (a[i]) {
        dp[i + 1][0] = (i - k) / 2 * dp[k][1] + (i - k + 1) / 2 * dp[k][0];
        dp[i + 1][1] = dp[k][0] + dp[k][1];
        k = i + 1;
      }
    printf("%I64d\n", dp[k][0] + dp[k][1]);
  }
  return 0;
}
