#include <iostream>
#include <unordered_map>
#include <vector>

bool calc_row(const int & row, std::unordered_map<int, int> & values, std::vector<int> & last_row, const int loking_for){
    bool returned_value = false;
    std::vector<int> new_row = {1};
    new_row.reserve(row);
    for (int i = 1; i < row - 1; ++i){
        new_row[i] = last_row[i-1] + last_row[i];
        auto n = values.find(new_row[i]);
        if (n == values.end()){
            if (new_row[i] == loking_for) returned_value = true;
            values.insert(n,{new_row[i], row});
        }
    }
    new_row[row-1] = 1;
    last_row.swap(new_row);
    return returned_value;
}

int main ( void ){

    int requests;
    std::cin >> requests;

    std::unordered_map<int, int> values;
    values.insert({1,1});
    int max_counted = 2;
    std::vector<int> last_row = {2};

    while (requests--){
        int look_for;
        std::cin >> look_for;
        if (values.find(look_for) == values.end()){
            bool found = false;
            do {
                found = calc_row(++max_counted, values, last_row, look_for);
            } while (!found);
        }
        std::cout << values[look_for] << "\n";
    }


}