#include <bits/stdc++.h>
using namespace std;
const unsigned long long inf = 1e9 + 10, N = 2e5 + 10, mod = 1e9 + 7, LG = 20;
long long t, n, m, f[100], cnt, dp[100], dp2[100], first;
bitset<100> b;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  m = 90;
  f[0] = 1;
  f[1] = 2;
  for (int i = 2; i < m; i++) f[i] = f[i - 1] + f[i - 2];
  cin >> t;
  while (t--) {
    b.reset();
    cin >> n;
    for (int i = m - 1; i >= 0; i--)
      if (n >= f[i]) {
        b.set(i);
        n -= f[i];
        first = i;
      }
    dp2[first] = first / 2;
    dp[first] = (first / 2) + 1;
    cnt = 0;
    for (int i = first + 1; i < m; i++) {
      if (b[i]) {
        if (cnt & 1) {
          dp2[i] = (cnt / 2) * dp[i - 1] + dp2[i - 1];
          dp[i] = (cnt / 2 + 1) * dp[i - 1] + dp2[i - 1];
        } else {
          dp2[i] = (cnt / 2) * dp[i - 1];
          dp[i] = (cnt / 2 + 1) * dp[i - 1];
        }
        cnt = 0;
      } else {
        dp[i] = dp[i - 1];
        dp2[i] = dp2[i - 1];
        cnt++;
      }
    }
    cout << dp[m - 1] << '\n';
  }
}
