#include <bits/stdc++.h>
using namespace std;
const int MAXN = 90, MOD = 1e9 + 7;
long long n, dpo[2], dp[2];
vector<long long> fib;
vector<int> de;
void solve() {
  cin >> n;
  de.clear();
  for (int i = fib.size() - 1; i >= 0; i--)
    if (n >= fib[i]) {
      de.push_back(i);
      n -= fib[i];
    }
  int ls = 0;
  dpo[0] = 0;
  dpo[1] = 1;
  reverse(de.begin(), de.end());
  for (int i = 0; i < de.size(); i++) {
    dp[0] = max(0, (de[i] - ls) / 2) * dpo[1];
    dp[0] += max(0, (de[i] + 1 - ls) / 2) * dpo[0];
    dp[1] = dpo[0] + dpo[1];
    swap(dp, dpo);
    ls = de[i] + 1;
  }
  cout << (dpo[1] + dpo[0]) % MOD << '\n';
}
int main() {
  fib.push_back(1), fib.push_back(2);
  while (fib.back() < 1e18) fib.push_back(fib.back() + fib[fib.size() - 2]);
  int t;
  cin >> t;
  while (t--) solve();
}
