#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

const long long inf = 1000000000000000000LL;

vector<long long> fib;
map<long long, int> f;

int solve(long long x) {
	if (f.count(x) > 0) return f[x];
	int t = lower_bound(fib.begin(), fib.end(), x) - fib.begin();
	if (fib[t] == x) {
		f[x] = 1;
		return 1;
	}
	int res = min(solve(fib[t] - x), solve(x - fib[t-1])) + 1;
	f[x] = res;
	return res;
}

int main() {
	fib.push_back(1);
	fib.push_back(2);
	long long a = 1, b = 2;
	while (true) {
		long long c = a + b;
		if (c > inf) break;
		fib.push_back(c);
		a = b;
		b = c;
	}
	
	int q;
	scanf("%d", &q);
	for (int i = 0; i < q; i ++) {
		long long x;
		scanf("%lld", &x);
		printf("%d\n", solve(x));
	}
	
	return 0;
}