#include <iostream>
#include <queue>
#include <set>

int readint() {
    int res;
    std::cin >> res;
    return res;
}

int generateNextDiagonal(
    int diag,
    std::set<std::pair<int, int>>& heap,
    std::vector<int>& previous,
    std::vector<int>& current,
    std::vector<int>& res
) {
    /*for(const int x : current) {
        std::cout << x << " " << std::flush;
    }
    std::cout << std::endl;*/

    // shift diagonals
    previous = current;
    current.resize(0);

    int found = 0;
    for(int i = 0; i < diag; i++) {
        if(i == 0) {
            current.push_back(1);
            continue;
        }
        int next;
        if(i == diag - 1)
            next = 2 * current[i - 1];
        else
            next = previous[i] + current[i - 1];
        current.push_back(next);

        auto it = heap.lower_bound({next, 0});
        //std::cout << next << " - "<< it->first << std::endl;
        while(it->first == next) {
            //std::cout << "found " << it->first << " at " << diag + i << std::endl;
            if(res[it->second] == 0) {
                res[it->second] = diag + i;
                found++;
            }
            ++it;
        }

        /*while(heap.top() == next) {
            heap.pop();
            std::cout << next << " na pozici " << diag + i << std::endl;
        }*/
    }
    return found;
}

int main() {

    std::set<std::pair<int, int>> search;
    int searchCount = readint();

    for(int i = 0; i < searchCount; ++i)
        search.insert({readint(), i});

    /*for(const auto x : search) {
        std::cout << x.first << " " << x.second << std::endl;
    }*/

    std::vector<int> previous{ 1 };
    std::vector<int> current{ 1, 2 };
    int i = 3;

    /*while(!search.empty()) {
        std::cout << search.top() << std::endl;
        search.pop();
    }
    return 0;*/

    std::vector<int> res(searchCount);
    int found = 0;

    auto it = search.lower_bound({1, 0});
    while(it->first == 1) {
        res[it->second] = 1;
        found++;
        ++it;
    }

    it = search.lower_bound({2, 0});
    while(it->first == 2) {
        res[it->second] = 3;
        found++;
        ++it;
    }

    while(found != searchCount) {
        found += generateNextDiagonal(i++, search, previous, current, res);
    }

    for(const int x : res) {
        std::cout << x << std::endl;
    }
    
    return 0;
}