#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_FIB = 110;
int fibonacci[MAX_FIB], value, test_cases;

inline int count_operations(int amount) {
    int operation_count = 0, index = 0;
    while (amount) {
        index = lower_bound(fibonacci + 1, fibonacci + 1 + 98, amount) - fibonacci;
        amount = min(amount - fibonacci[index - 1], fibonacci[index] - amount);
        operation_count++;
    }
    return operation_count;
}

inline void initialize() {
    scanf("%lld", &test_cases);
    fibonacci[1] = 1;
    for (int i = 2; i <= 98; i++) {
        fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
    }
    while (test_cases--) {
        scanf("%lld", &value);
        printf("%lld\n", count_operations(value));
    }
}

signed main() {
    initialize();
    return 0;
}