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

int max = 0;

int get_value(std::unordered_map<int, int> m, int key) {
    auto iter = m.find(key);
    if (iter == m.end()) {
        return -1;
    } else {
        return iter->second;
    }
}

std::vector<int> *generate_line(std::vector<int> *prev,
                                std::unordered_map<int, int> &m, int row) {
    int size = prev->size();
    auto result = new std::vector<int>();
    result->push_back(1);
    for (int i = 0; i < size - 1; i++) {
        int key = prev->at(i) + prev->at(i + 1);
        if (get_value(m, key) == -1) {
            m[key] = row;
        }
        result->push_back(key);
        max = std::max(key, max);
    }
    result->push_back(1);
    return result;
}


int main() {
    int q, n, max_n = 0;
    std::vector<int> *prev = new std::vector<int>();
    prev->push_back(1);
    std::unordered_map<int, int> m;
    m[1] = 1;
    scanf("%d", &q);
    int line = 2;
    for (int i = 0; i < q; ++i) {
        scanf("%d", &n);
        int value = get_value(m, n);
        while (value == -1) {
            auto new_line = generate_line(prev, m, line);
            delete prev;
            prev = new_line;
            value = get_value(m, n);
            line++;
        }
        printf("%d\n", get_value(m, n));
    }


    return 0;
}