#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*i <= x; i+=2) {
        if(x%i == 0)
            out.push_back(i);
        while(x%i ==0)
            x/=i;
        //cout << i << endl;
    }
    if (x!= 1)
        out.push_back(x);
    return out;
}

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a%b);
}

int vydel(unordered_set<int> &h, unordered_set<int> &dole) {
    vector<int> hore(h.begin(), h.end());
    for (auto x: dole) {
        for (int i = 0; i < hore.size(); ++i) {
            int gc = gcd(hore[i], x);
            hore[i] /= gc;
            x/=gc;
        }
    }
    int prod = 1;
    for (auto x : hore)
        prod *= x;
    return prod;
}

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 = rozklad[rozklad.size()-1];
            int n = nejvetsi;
            if (n == N) {
                cout << n + 1 << '\n';
                continue;
            }
            while (true) {
                unordered_set<int> hore;
                hore.insert(n);
                unordered_set<int> dole;
                dole.insert(1);
                int k = 1;
                int add = 1;
                int hd = n;
                while (n / 2 >= (k+add) && hd < N && n-add > 0) {
                    //cout << n - add << ' ' << k + add << endl;
//                    dole *= k + add;
//                    hore *= n - add;
                    int pridat_dolu = k+add;
                    int pridat_nahoru = n - add;
                    int gc = gcd(pridat_nahoru, pridat_dolu);
                    pridat_nahoru /= gc;
                    pridat_dolu /= gc;
                    hd *= pridat_nahoru;
                    hd /= pridat_dolu;
                    add++;
                    //hd = vydel(hore, dole);
                }
                if (hd == N) {
                    cout << n+1 << '\n';
                    break;
                }
                n++;
            }
        }
    }





	return 0;
			
}