#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010000,maxm = 763560 + 10000;

int tot,t,x,who;
bool b[maxn];
int nxt[maxm];

inline bool check(int x){
	int pd = 0;
	while(x){
		pd = x%10,x/=10; 
		if(pd == 7) return 1;
 	}
	return 0;
}
void pre(){
	for(int i=1;i<maxn-1;i++){
		if(b[i]) continue;
		if(check(i)) for(int j=i;j<maxn-1;j+=i) b[j] = 1;
		else nxt[++tot] = i;
	}
}
int main(){
	pre();
//	cout<<tot<<endl;
	//tot max -> 763560
	scanf("%d",&t);
	while(t--){
		scanf("%d",&x);
		if(b[x]) printf("%d\n",-1);
		else who = upper_bound(nxt+1,nxt+1+tot,x) - nxt,printf("%d\n",(who <= tot && who >= 1) ? nxt[who] : -1);
	}
	/*
	WA 70
	输入的 x 到 1e7，输出的下一个数可能超过 1e7。
	记得开大点数组，筛多点数。
	*/
	return 0;
}

AC

预处理 $nlogn$ (或者是 $nloglogn$ ?)

查询 $T(logm)$