#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>

int main() {
  // Calculate fibonacci numbers.
  std::vector<std::int64_t> fib_nums;
  std::int64_t a = 0;
  std::int64_t b = 1;
  fib_nums.push_back(a);
  fib_nums.push_back(b);
  for (;;) {
    if (a > std::numeric_limits<std::int64_t>::max() - b) {
      break;
    }
    std::int64_t c = a + b;
    fib_nums.push_back(c);
    a = b;
    b = c;
  }

  // Num test cases.
  std::size_t p;
  std::cin >> p;

  while (p--) {
    std::int64_t k;
    std::cin >> k;

    std::size_t n = 0;
    while (k > 0) {
      auto lower_bound = std::lower_bound(fib_nums.begin(), fib_nums.end(), k);
      // a < k <= b
      std::int64_t a = *(lower_bound - 1);
      std::int64_t b = *lower_bound;
      // greedy
      k = std::min(k - a, b - k);
      ++n;
    }
  
    std::cout << n << '\n';
  }

  return 0;
}