#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e7+500;
bool isp[maxn];
const int maxp=1e7+500;
int p[maxp],m=0;
void ol(int n){
    for(int i=2;i<=n;i++)isp[i]=1;
    for(int x=2;x<=n;x++){
        if(isp[x]){
            p[++m]=x;
        }
        for(int i=1;i<=m&&p[i]*x<=n;i++){
            isp[p[i]*x]=0;
            if(x%p[i]==0)break;
        }
    }
}
bool f[maxp];
int q,n;
signed main(){
	cin>>q;
	ol(10000100);
	for(int i=1;i<=q;i++){
		scanf("%lld",&n);
		int k=upper_bound(p+1,p+1+m,n)-p;
		cout<<p[k]<<"\n";
	}
	return 0;
}