#include <bits/stdc++.h>
#define ll long long
#define N 1000000
using namespace std;
ll a[N+5];
bool prime[N+5];
void sang()
{
    fill(prime,prime+N+3,1);
    prime[1]=prime[0]=0;
    for(int i=2;i*i<=N;i++){
        if(prime[i]){
            for(int j=i*i;j<=N;j+=i){
                prime[j]=0;
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ///anh đẳng cấp
    freopen("NGUYENTOKEP.inp","r",stdin);
    freopen("NGUYENTOKEP.out","w",stdout);
    int t;
    sang();
    int quanlon=1;
    for(ll i=1;i<=N;i++){
        if(prime[i]){
            for(ll j=i+1;j*i<=N;j++){
                if(prime[j]){
                    a[quanlon]=j*i;
                    quanlon++;
                }
            }
        }

    }
    sort(a+1,a+N+1);
    cin>>t;
    while(t--){
        int hehe;
        cin>>hehe;
        int bruh=upper_bound(a+1,a+1000003,hehe)-a-1;
        cout<<a[bruh]<<'\n';
    }
    return 0;
}
