#include <bits/stdc++.h>
#define N 1000005
using namespace std;
bool nt[N];
void sang()
{
    for (int i=0;i<=N;i++)
    {
        nt[i]=true;
    }
    nt[0]=nt[1]=false;
    for(int i=2;i*i<=N;i++)
    {
        if (nt[i])
        {
            for (int j=i*i;j<=N;j+=i)
            {
                nt[j]=false;
            }
        }
    }
}
int main()
{
   freopen("CAU3.INP","r",stdin);
    freopen("CAU3.OUT","w",stdout);
    sang();
    long long t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        while(!nt[n])e
        {
            n++;
        }
        cout<<n<< endl;
    }
    return 0;
}
