#include<cstdio>
#define itn int
#define logn long
#define ll long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int prime[10000000],cnt=0;
bool isnotprime[100000000];
void sieve(int qw){
	for(int i=2;i<=qw;i++){
        if(!isnotprime[i]){
			prime[++cnt]=i;
		}
		for(int j=1;j<=cnt&&i*prime[j]<=qw;j++){
			isnotprime[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
bool pig(int n){
    while(n>1){
        if(n%10==7)return 0;
        n=n/10;
    }
    return 1;
}
int check(int n){
    if(n==1)return 1;
    if(pig(n)==0||n%7==0)return -1;
    if(isnotprime[n]==0)return 1;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            if(pig(i)==0||pig(n/i)==0){
                return -1;
            }
        }
    }
    return 1;
}
signed main(){
    int t;
    t=read();
    sieve(10000000);
    while(t--){
        int n;
        n=read();
        int cnt=check(n);
        if(cnt==-1)puts("-1");
        else{
            for(int j=n+1;j<=2e7;j++){
                if(check(j)==1){
                    printf("%d\n",j);
                    break;
                }
            }
        }
    }
}