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

void calc_row(const int & row, std::unordered_map<int, int> & values, std::vector<int> & last_row){
    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];
        if (values.find(new_row[i]) == values.end()){
            values.insert({new_row[i], row});
        }
    }
    new_row[row-1] = 1;
    last_row.swap(new_row);
}

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()){
            do {
                calc_row(++max_counted, values, last_row);
            } while (values.find(look_for) == values.end());
        }
        std::cout << values[look_for] << "\n";
    }


}