#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=2e5+1,M=1e7+1;
int t,x[N],p[M],nxt[M],maxn=-1;
bool have7(int num){
	while(num>0){
		if(num%10==7) return 1;
		else num/=10;
	}
	return 0;
}
void update(int st){
	for(int i=st;i<=M;i+=st){
		p[i]=1;
	}
}
int main(){
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	scanf("%d",&t);
	for(int i=1;i<=M;i++){
		if(p[i]) continue;
		else if(i%7==0) update(i);
		else if(have7(i)) update(i);
	}
	for(int i=1;i<=t;++i){
		scanf("%d",&x[i]);
		if(p[x[i]]) printf("-1\n");
		else if(nxt[x[i]]) printf("%d\n",nxt[x[i]]);
		else{
			int j=x[i]+1;
			while(p[j]) j++;
			int k=j;
			while(p[k]) --k,nxt[k]=j;
			printf("%d\n",j);
		}
	}
	return 0;
}