#include <bits/stdc++.h>
#define N 10000007
using namespace std;
long long 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;
            }
        }
    }
}
long long n,t;
int main(){
    sang();
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("CAU3.INP","r",stdin);
    freopen("CAU3.OUT","w",stdout);
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>n;
        for(int j=1;j<=1000000;j++){
            if(p[j] && j>=n){
                cout<<j<<'\n';
                break;
            }
        }
    }
    return 0;
}
