#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<string.h>

using namespace std;

int t,x;

bool vis[10000010];

bool judge(int aa)

{

    while(aa!=0)

	{

        if(aa%10==7)return true;

        aa/=10;

    }

    return false;

}

void chushi()

{

    for(int i=1;i<=10000000;i++)

	{

        if(vis[i])continue;

        if(judge(i)){

            for(int j=i;j<=10000000;j+=i)

			{

                if(vis[j])continue;

                vis[j]=true;

            }

        }

    }

}

int main()

{

	chushi();

    scanf("%d",&t);

    for(int i=1;i<=t;i++)

	{

        scanf("%d",&x);

        if(vis[x])

			printf("-1\n");

        else

		{

            int k=x+1;

            while(k>0)

			{

                if(vis[k]==0)

				{

                    printf("%d\n",k);

                    break;

                }

                k++;

            }

        }

    }

    return 0;

}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<string.h>

#include<cstdlib>

using namespace std;

int t,x,ans[10000010];

bool vis[10000010];

bool judge(int aa)

{

    while(aa!=0)

	{

        if(aa%10==7)return true;

        aa/=10;

    }

    return false;

}

void chushi()

{

    for(int i=1;i<=10000000;i++)

	{

        if(vis[i])continue;

        if(judge(i)){

            for(int j=i;j<=10000000;j+=i)

			{

                if(vis[j])continue;

                vis[j]=true;

            }

        }

    }

}

int main()

{

	chushi();

    scanf("%d",&t);

    for(int i=1;i<=t;i++)

	{

        scanf("%d",&x);

        if(vis[x])

			printf("-1\n");

		else if(ans[x]!=0)printf("%d\n",ans[x]);

        else

		{

            int k=x+1;

            while(k>0)

			{

                if(vis[k]==0)

				{

                    printf("%d\n",k);

                    ans[x]=k;

                    break;

                }

                k++;

            }

        }

    }

    return 0;

}