#include<iostream>
#include<cstdio>
using namespace std;
int ans[10000001], todo, maxx = -1;//若i不能报，则ans[i]存-1，否则存 下一个应该报的数，todo存当前最后一个需要处理的数 
int qq[200001];
void solve()//离线处理答案 
{
    for(int i = 1; ans[maxx] == 0; i++)
    {
        if(i == 1)//特判 
        {
            ans[i] = 2;
            todo = i;
            continue;
        }
        if(ans[i] == -1)
            continue;
        int x = i, flag = 1;
        while(x)//判断当前的数是否含有数字7 
        {
            if(x % 10 == 7)
            {
                flag = 0;
                break;
            }
            x /= 10;
        }
        if(!flag)//筛 
        {
            for(int j = 1; i * j <= 10000005; j++)
                ans[i * j] = -1;
        }
        if(ans[i] == 0)//如果这个数可以报 
        {
            ans[todo] = i;//那么对于当前最后一个不知道该报啥的数应该报这个数 
            todo = i;//这个数还不知道报啥 
        }
    }
}
int n, xx;
int main()
{
    todo = 1;
    ans[10000000] = 10000001;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &qq[i]);
        maxx = max(qq[i], maxx);
    }
    solve();
    for(int i = 1; i <= n; i++)
        cout << ans[qq[i]] << endl;
    return 0;
}