#include <bits/stdc++.h>
#define ll long long
#define N 1000000
using namespace std;
ll p[N];
void sang(){
    memset(p,1,sizeof(p));
    p[0] = p[1] = 0;
    for(int i = 2;i*i <= N;i++){
        if(p[i]){
            for(int j = i*i;j <= N;j+=i){
                p[j] = 0;
            }
        }
    }
}
ll q,n;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    freopen("CAU3.INP","r",stdin);
    freopen("CAU3.OUT","w",stdout);
    sang();
    cin >> q;
    while(q--){
        cin >> n;
        while(!p[n]){
            n++;
        }
        cout <<n<<endl;
    }
    return 0;
}
