#include<bits/stdc++.h> 
using namespace std;
int a,vist[10000000];
int sum=1,n;
int jis=0;
void baoshu()
{
	for(int i=6;i<=jis+10000000;i++)
	{
		int g=i,f=i;
		if(vist[g]==0)
		{
			while(f>1)
			{
				if(f%10==7)
				{
					for(int z=g;z<=jis+10000000;z=z+g)
					{
						vist[z]=1;
					}
					break;
				}
				f=f/10;
			}
		}
	}
}
int main()
{
	cin>>n;
	baoshu();
	for(int j=1;j<=n;j++)
	{
		cin>>a;
		if(vist[a]==1)
		{
			cout<<-1<<endl;
			continue;
		}
		for(int sum=a; ;sum++)
		{
			if(vist[sum]==0&&sum>a)
			{
				cout<<sum<<endl;
				break;
			}
		}
	}
	return 0;
}