#include <cstdio>

using namespace std;

int c[1000001],v[1000001],b[1000001][8];

int main()
{
    int i,j,k,n,t;
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    for (i=2;i<=1000000;++i)
        if (!v[i])
        {
            c[i]=1;
            for (j=2*i;j<=1000000;j+=i)
            {
                ++c[j];
                v[j]=1;
            }
        }
    for (i=1;i<=1000000;++i)
    {
        for (j=0;j<=7;++j)
            b[i][j]=b[i-1][j];
        if (c[i]<=7)
            b[i][c[i]]=i;
    }
    scanf("%d",&t);
    for (i=1;i<=t;++i)
    {
        scanf("%d%d",&n,&k);
        printf("%d\n",b[n][k]);
    }
    return 0;
}