#include <bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
ll a[1000005],t;
bool nt[N];
void snt()
{
    nt[0]=nt[1]=false;
    for (int i=2;i<=N;i++)
        nt[i]=true;
    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()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("CAU3.INP","r",stdin);
    freopen("CAU3.OUT","w",stdout);
    cin>>t;
    snt();
    while (t--)
    {
        ll n;
        cin>>n;
        for (int i=n;i<=n+100;i++)
        {
            if (nt[i])
            {
                cout<<i<<endl;
                break;
            }
        }
    }
    return 0;
}
