#include <cstdio>

using namespace std;
const int N=1000000;
int a[8][N],d[N],nr[8];
int caut(int v[],int y,int x)
{
    int i=0,pas=1<<18;
    while(pas!=0)
    {
        if(i+pas<=y&&v[i+pas]<=x)
            i+=pas;
        pas/=2;
    }
    return i;
}
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int nd,i,j,k,n,t,ndiv;
    n=N;
    for(i=2;i<=n;i++)
        if(d[i]==0)
            for(j=i;j<=n;j+=i)
                d[j]++;
    for(i=1;i<=n;i++)
    {
        ndiv=d[i];
        nr[ndiv]++;
        nd=nr[ndiv];
        a[ndiv][nd]=i;
    }
    scanf("%d", &t);
    for(i=1;i<=t;i++)
    {
        //cin>>n>>k;
        scanf("%d%d", &n, &k);
        nd = caut(a[k],nr[k],n);
        //cout<<a[k][nd]<<"\n";
        printf("%d\n", a[k][nd]);
    }
    return 0;
}