#include<bits/stdc++.h>
using namespace std;
const int N=1e7+1000;
bool re[N],pw[N];
int pre[26000000],m,n,t,cnt;
void _init(){
	re[7]=true;
	for(int j=0;j<=9;++j) re[70+j]=true;
	for(int i=1;i<N;++i){
		if(re[i]){
			if(!pw[i]) for(int j=2;j<N/i;++j) pw[i*j]=true;
			for(int j=0;j<=9;++j) if(i*10+j<N) re[i*10+j]=true;
		}
		if(!re[i]&&!pw[i]) pre[++cnt]=i;
		if(i*10+7<N) re[i*10+7]=true;
	}
}
int main(){
	scanf("%d",&t);
	_init();
	for(int i=1;i<=t;++i){
		scanf("%d",&m);
		if(re[m]||pw[m]) printf("-1\n");
		else printf("%d\n",pre[lower_bound(pre,pre+cnt,m)-pre+1]);
	}
	return 0;
}