#include<bits/stdc++.h>
using namespace std;
int p[1000005],nx[1000005];
int main()
{
	memset(nx,-1,sizeof(nx));	
	for (int i=1;i<=100000;i*=10)
		for (int left=0;left<=100000/i;left++)
			for (int right=0;right<i;right++) 
				p[left*10*i+7*i+right]=2;
	for (int i=7;i<=1000000;i+=7)p[i]=1;	
	for (int i=17;i<=500000;i++)
	{
		if(p[i]==2)
		{
			for (int j=i+i;j<=1000000;j+=i)p[j]=3;
		}
	}
	int s=1,t;
	for (int i=2;i<=1000000;i++)
		if (!p[i])
		{
			nx[s]=i;
			s=i;
		}
	scanf("%d",&t);
	while (t--)
	{
		scanf("%d",&s);
		printf("%d\n",nx[s]);
	}
	return 0;
}