#include <cstdio>

using namespace std;
int ciur[1000001],v[8];
int mat[8][1000000];
int main()
{
    FILE *fin=fopen ("divprim.in","r");
    FILE *fout=fopen ("divprim.out","w");
    int d,i,dp,n,t,st,dr,mid;
    for (d=2;d<=1000000;d++){
        if (ciur[d]==0){
            ciur[d]=1;
            for (i=2*d;i<=1000000;i+=d)
                ciur[i]++;
        }
    }
    for (i=1;i<=1000000;i++){
        dp=ciur[i];
        mat[dp][++v[dp]]=i;
    }
    fscanf (fin,"%d",&t);
    for (;t;t--){
        fscanf (fin,"%d%d",&n,&dp);
        st=1;
        dr=v[dp];
        while (st<=dr){
            mid=(st+dr)/2;
            if (mat[dp][mid]<=n)
                st=mid+1;
            else dr=mid-1;
        }
        fprintf (fout,"%d\n",mat[dp][dr]);
    }
    return 0;
}