#include<cstdio>
using namespace std;
int ma[8][1000001],ciu[1000001];
void ciurific()
{
    int j;
    int mas=1000000;
    for(int i=2; i<=mas; i++)
    {
        for(j=1;j<=7;j++)
        {
            ma[j][i]=ma[j][i-1];
        }
        if(ciu[i]==0)
        {
            for(j=2*i; j<=mas; j+=i)
            {
                ciu[j]++;
            }
            ma[1][i]=i;
        }
        else
        {
            if(ciu[i]<=7)
            {
                ma[ciu[i]][i]=i;
            }
        }
    }
}
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    ciurific();
    int n,i,a,b;
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        scanf("%d %d ",&a,&b);
        printf("%d\n",ma[b][a]);
    }
    return 0;
}