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

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

const int LIM = 1e5;
bitset<LIM> isPrime;

vector<int> erastothenes() {
    const int S = (int) round(sqrt(LIM)), R = LIM/2;
    vector<int> pr = {}, sieve(S+1); pr.reserve(int(LIM/log(LIM)*1.1));
    vector<pair<int, int>> cp;
    for (int i = 3; i <=S; i+= 2) if (!sieve[i]) {
        cp.push_back({i, i*i/2});
        for (int j = i*i; j<=S;j+=2*i) sieve[j] = 1;
    }
}


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 = primes2(N);
            int n = nejvetsi;
            if (n == N) {
                cout << n + 1 << '\n';
                continue;
            }
            while (true) {
                int k = 1;
                int add = 1;
                ll hd = n;
                while (n / 2 >= (k+add) && hd < N && n-add > 0) {
                    ll pridat_dolu = k+add;
                    ll pridat_nahoru = n - add;
                    //int gc = gcd(pridat_nahoru, pridat_dolu);
                    //pridat_nahoru /= gc;
                    //pridat_dolu /= gc;
                    hd *= pridat_nahoru;
                    hd /= pridat_dolu;
                    add++;
                }
                if (hd == N) {
                    cout << n+1 << '\n';
                    break;
                }
                n++;
            }
        }
    }





	return 0;
			
}