#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#define ll long long

vector<int> primes(int x) {
    vector<int> out;
    if (x % 2 == 0)
        out.push_back(2);
    while (x%2 == 0)
        x/= 2;
    for (int i = 3; i <= x; i+=2) {
        if(x%i == 0)
            out.push_back(i);
        while(x%i ==0)
            x/=i;
        //cout << i << endl;
    }
    return out;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

    vector<vector<int>> komb(1000, vector<int>(1000));
    vector<unordered_set<int>> toq(1000, unordered_set<int>());
    for (int i = 0; i < 1000; ++i)
    {
        komb[i][0] = 1;
        komb[i][i] = 1;
        toq[i].insert(1);

    }
    int ma = 0;
    for (int i = 1; i < 1000; i++)
    {
        for(int j = 1; j < i; j++)
        {
            komb[i][j] = komb[i-1][j] + komb[i-1][j-1];
            toq[i].insert(komb[i][j]);
            ma = max(ma, komb[i][j]);
        }
    }
    //cout << ma;
    int Q; cin >> Q;
    for (int i = 0; i < Q; ++i) {
        //cout << i << "Q" << Q << endl;
        int N; cin >> N;
        bool solved = false;
        /*for (int i = 0; i < 1000; ++i) {
            if(toq[i].find(N) != toq[i].end()) {
                cout << i + 1 << endl;
                solved = true;
                break;
            }
        }*/
        if (N == 1) {
            cout << "1\n";
            solved=true;
        }
        if (!solved) {
            auto rozklad = primes(N);
            int nejvetsi = -1;
            for (auto x: rozklad) {
                nejvetsi = max(nejvetsi, x);
            }
            int n = nejvetsi;
            if (n == N) {
                cout << n + 1 << '\n';
                continue;
            }
            while (true) {
                int hore = n;
                int dole = 1;
                int k = 1;
                int add = 1;
                while (hore / dole < N) {
                    //cout << n - add << ' ' << k + add << endl;
                    hore *= n - add;
                    dole *= k + add;
                    add++;
                }
                if (hore / dole == N) {
                    cout << n+1 << '\n';
                    break;
                }
                n++;
            }
        }
    }





	return 0;
			
}