#include <bits/stdc++.h>
using namespace std;
int calc(int n) { return n / 2 + 1; }
int main() {
  long long NUM = 1000000;
  NUM *= NUM * NUM;
  vector<long long> fibo;
  fibo.push_back(1);
  fibo.push_back(2);
  for (int a = 0;; a++) {
    long long k = fibo[a] + fibo[a + 1];
    if (k < NUM)
      fibo.push_back(fibo[a] + fibo[a + 1]);
    else
      break;
  }
  reverse(fibo.begin(), fibo.end());
  int k = fibo.size();
  int t;
  cin >> t;
  for (int z = 0; z < t; z++) {
    long long n;
    cin >> n;
    vector<int> check;
    for (int a = 0; a < k; a++) {
      int p = 0;
      if (fibo[a] <= n) n -= fibo[a], p = 1;
      check.push_back(p);
    }
    reverse(check.begin(), check.end());
    long long x = 1;
    long long y = 0;
    int prev = -1;
    int key = 0;
    while (check.size() > key) {
      if (check[key] == 1) {
        int st = key - prev - 1;
        long long xx = x + y;
        long long yy = x * (calc(st) - 1) + y * (calc(st + 1) - 1);
        x = xx;
        y = yy;
        prev = key;
      }
      key++;
    }
    cout << x + y << endl;
  }
  return 0;
}
