#include<bits/stdc++.h>
using namespace std;
int t[10000000],b[100000000],aa[10000000];
int n;
int ans[10000000];
int main() {
	for(int i=1;i<=10000000;i++) {
		int a=i;
		if(t[i]==1) continue;
		while(a>0) {
			if(a%10==7) {
				t[i]=1;
				break;
			}
			a/=10;
		}
		if(t[i]==1) for(int j=1;j<=10000000/i+1;j++) t[i*j]=1;
	}
	int l=10000001;
	for(int i=10000000;i>=1;i--) {
		b[i]=l;
		if(!t[i]) l=i; 
	}
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>aa[i];
		if(t[aa[i]]==1) {
			ans[i]=-1;
			continue;
		}
		ans[i]=b[aa[i]];
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
    return 0;
}