#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <map>
#include <set>

typedef unsigned long long int ulli;

ulli fact(int n, std::vector<ulli>& factCache)
{
    ulli lastFact = factCache[factCache.size() - 1];
    if (factCache.size() > n)
    {
        return factCache[n];
    }
    for (int i = factCache.size(); i <= n; ++i)
    {
        factCache.push_back(lastFact * i);
        lastFact *= i;
    }
    return factCache[n];
}

ulli binomial(int n, int k, std::vector<ulli>& factCache)
{
    return (fact(n, factCache)) / ((fact(k, factCache)) * (fact((n-k), factCache)));
}

struct binomialNum
{
    std::pair<int, int> duo;
    ulli val;

    bool operator <(const binomialNum& other) const
    {
        return val < other.val;
    }
};

int solve(std::vector<ulli>& cache)
{
    int input;
    std::cin >> input;

    if (input == 1)
        return 1;

    std::priority_queue<binomialNum, std::vector<binomialNum>, std::less<>> q;
    std::set<binomialNum> map;

    binomialNum first = {std::make_pair(2, 1), 2 };

    q.push(first  );
    map.insert(first);

    while (!q.empty())
    {
        binomialNum current = q.top();
        map.insert(current);

        ulli left = ((current.val) * current.duo.second)/(current.duo.first - current.duo.second + 1);
        ulli right = (current.val) * ((current.duo.first - current.duo.second)/(current.duo.second + 1));

        ulli aVal = left + current.val;
        ulli bVal = right + current.val;

        binomialNum nextA = {std::make_pair(current.duo.first + 1, current.duo.second), aVal};
        binomialNum nextB = {std::make_pair(current.duo.first + 1, current.duo.second + 1), bVal};




        if (aVal == input || bVal == input)
            return nextA.duo.first + 1;

        bool containsA = map.find(nextA) != map.end();
        bool containsB = map.find(nextB) != map.end();

        q.pop();


        if (aVal == bVal)
        {
            if (aVal < input && !containsA) {
                q.push(nextA);
            }
        }
        else
        {
            if (aVal < input && !containsA) {
                q.push(nextA);
            }

            if (bVal < input && !containsB)
            {
                q.push(nextB);
                }

            }
    }
    return -1;
}

int main() {

    std::vector<ulli> factCache;
    factCache.push_back(1);
    factCache.push_back(1);

    int input;

    std::cin >> input;

    for (int i = 0; i < input; ++i)
    {
        std::cout << solve(factCache) << std::endl;
    }


    return 0;
}