#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;

ll n,mi=0x3f3f3f,ma=-2147483647;
ll num[2000010];
bool p[10000101];

int main()
{
    scanf("%lld",&n);

    for(ll i=1; i<=10000001;i++) {
        if(to_string(i).find('7')!=-1) {
            p[i]=1;
            for(ll j=i*2; j<=10000001; j+=i)
                p[j]=1;
        }
    }

    for(ll i=1; i<=n; i++) {
        scanf("%lld",&num[i]);
        ma=max(ma,num[i]);
        if(p[num[i]]==1) {
            printf("-1\n");
            continue;
        }
        for(ll j=num[i]+1; j<=ma+10001; j++) {
            if(p[j]==0) {
                 printf("%lld\n",j);
                 break;
            }
        }
    }

    return 0;
}