#include<bits/stdc++.h>

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define rep(i,n) for( ll i = 0; i < n; ++i )
#define repi(i,n) for( ll i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( ll j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef unsigned int ll;
#define vll vector<ll>
using namespace std;

vll a(63248 , 0);
ll j = 1;

inline bool prime(ll d){
    ll i = 1;
    while(a[i]*a[i] <= d){
        if(i > j) break;
        if(d % a[i] == 0) return 0;
        ++i;
    }
    return 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(0);
    a[1] = 2;
    repf(i , 3 , 63248)
        if(prime(i)) a[++j] = i;
    ll t , n;
    cin >> t;
    repi(i , t){
        cin >> n;
        ++n;
        if(n == 1) ++n;
        for(;;){
            if(prime(n)){
                die(n);
                break;
            }else ++n;
        }
    }
    return 0;
}