#include <bits/stdc++.h>
inline long long getint() {
  register char ch;
  while (!isdigit(ch = getchar()))
    ;
  register long long x = ch ^ '0';
  while (isdigit(ch = getchar())) x = (((x << 2) + x) << 1) + (ch ^ '0');
  return x;
}
long long f[87][2], c[87],
    fib[87] = {0,
               1,
               2,
               3,
               5,
               8,
               13,
               21,
               34,
               55,
               89,
               144,
               233,
               377,
               610,
               987,
               1597,
               2584,
               4181,
               6765,
               10946,
               17711,
               28657,
               46368,
               75025,
               121393,
               196418,
               317811,
               514229,
               832040,
               1346269,
               2178309,
               3524578,
               5702887,
               9227465,
               14930352,
               24157817,
               39088169,
               63245986,
               102334155,
               165580141,
               267914296,
               433494437,
               701408733,
               1134903170,
               1836311903,
               2971215073ll,
               4807526976ll,
               7778742049ll,
               12586269025ll,
               20365011074ll,
               32951280099ll,
               53316291173ll,
               86267571272ll,
               139583862445ll,
               225851433717ll,
               365435296162ll,
               591286729879ll,
               956722026041ll,
               1548008755920ll,
               2504730781961ll,
               4052739537881ll,
               6557470319842ll,
               10610209857723ll,
               17167680177565ll,
               27777890035288ll,
               44945570212853ll,
               72723460248141ll,
               117669030460994ll,
               190392490709135ll,
               308061521170129ll,
               498454011879264ll,
               806515533049393ll,
               1304969544928657ll,
               2111485077978050ll,
               3416454622906707ll,
               5527939700884757ll,
               8944394323791464ll,
               14472334024676221ll,
               23416728348467685ll,
               37889062373143906ll,
               61305790721611591ll,
               99194853094755497ll,
               160500643816367088ll,
               259695496911122585ll,
               420196140727489673ll,
               679891637638612258ll};
int main() {
  for (register int T = getint(); T; T--) {
    long long n = getint();
    int cnt = 0;
    for (register int p = std::lower_bound(&fib[1], &fib[87], n) - fib; p;
         p--) {
      if (n >= fib[p]) {
        n -= fib[p];
        c[++cnt] = p;
      }
    }
    std::reverse(&c[1], &c[cnt] + 1);
    f[1][0] = 1;
    f[1][1] = (c[1] - 1) / 2;
    for (register int i = 2; i <= cnt; i++) {
      f[i][0] = f[i - 1][0] + f[i - 1][1];
      f[i][1] = f[i - 1][0] * ((c[i] - c[i - 1] - 1) / 2) +
                f[i - 1][1] * ((c[i] - c[i - 1]) / 2);
    }
    printf("%lld\n", f[cnt][0] + f[cnt][1]);
  }
  return 0;
}
