#include<bits/stdc++.h>
using namespace std;
int t;
int tet=0;
struct ies{
	int name;
	int nxt;
}mus[111222333];
bool could[111222333];
inline bool ioc(int x){
	do{
		if(x%10==7){
			return 1;
		}
	}while(x/=10);
	return 0;
}
int main(){
	//freopen("number4.in","r",stdin);
	//freopen("number.ans","w",stdout);		
	scanf("%d",&t);
	for(register int i=1;i<=t;i++){
		scanf("%d",&mus[i].name);
		mus[i].nxt=mus[i].name+1;
		tet=max(tet,mus[i].name);
	}
	
	for(register int i=1;i<=tet+tet/2;i++){
		if(could[i]==1){
			continue;
		}
		if(ioc(i)==1){
			could[i]=1;
			for(register int j=i;j<=tet+tet/2;j+=i){
				could[j]=1;
			}
		}
	}
	
	for(register int i=1;i<=t;i++){
		if(could[mus[i].name]==0&&could[mus[i].nxt]==1){
			for(register int j=mus[i].nxt;j<=tet+tet/2;j++){
				if(could[j]==0){
					mus[i].nxt=j;
					break;
				}
			}
		}
	}
	for(register int i=1;i<=t;i++){
		if(could[mus[i].name]){
			printf("-1\n");
		}
		else{
			printf("%d\n",mus[i].nxt);
		}
	}
	return 0;
}