#include<bits/stdc++.h>
using namespace std;
const int N=1e7+500;
int x,t,vis[N],flag,cnt,p[N],s;
void ela()
{
	for(int i=7;i<=1e7+500;i++)
	{
		int temp=i;
		if(!vis[i])
		{
			while(temp!=0)
		{
			 s=temp%10;
			if(s==7) 
			{
				flag=1;break;
			}
			temp/=10;
		}
		if(flag)
		{
			p[++cnt]=i,vis[i]=1;
		 for(int j=2;j*i<=1e7+500;j++)
		{
			vis[j*i]=1;
//			if(i%j==0&&vis[j]) break;
		}
		
		}
		if(!flag)
		{
			for(int j=1;j<=cnt&&p[j]*i<=1e7+500;j++)
			{
				vis[p[j]*i]=1;
		//		if(i%p[j]==0) break;
			}
		}
		flag=0;s=0;
	}
	else 
	{
		for(int j=1;j<=cnt&&p[j]*i<=1e7+500;j++)
			{
				vis[p[j]*i]=1;
		//		if(i%p[j]==0) break;
			}
	}
}
}
int main()
{
//	freopen("P7960_1.in","r",stdin);
//	freopen("number(3).out","w",stdout);
	cin>>t;
	int w=time(0);
	ela();
//	;
	for(int i=1;i<=t;i++)
	{
		cin>>x;
		
			if(vis[x])
			{
				cout<<"-1"<<endl;continue;
			}
			for(int j=x+1;;j++)
			{
				if(!vis[j]) 
				{
					cout<<j<<endl;break;
				}
			}
		
	}
//	cout<<time(0)-w;
	return 0;
}