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

bool is_prime(int n) {
    for(int i = 2; i * i <= n; ++ i)
        if(n % i == 0)
            return false;
    return true;
}

vector<bool> prime(1e6 + 1, true);
void sieve() {
    prime[0] = prime[1] = false;
    for(int i = 2; i <= 1e6; ++ i) {
        if(prime[i]) {
            for(int j = i * 2; j <= 1e6; j += i) {
                prime[j] = false;
            }
        }
    }
}

int32_t main() {
    int q; cin >> q;
    if(q > 100) sieve();
    for(int i = 0; i < q; ++ i) {
        int n; cin >> n;
        if(q <= 100) {
            while(!is_prime(n)) ++ n;
        }
        else {
            while(!prime[n]) ++ n;
        }
        cout << n << "\n";
    }
}