#include <stdio.h>
#include <bitset>

using namespace std;

long N,k,i,j,p[3000],ok,q,x,d;
long a[8][500000],T,low,mid,high,l[8],maxim,ndp[1000005];
bitset <1000005>prim;

int main(){
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    
    prim.set();
    prim[1]=0;
    for (i=2;i<=1000000;i++)
        if (prim[i]){
           for (j=i+i;j<=1000000;j+=i)
           prim[j]=0;
    }

    for (i=1;i<=1000000;++i)
        if (prim[i]==1){
           maxim=1000000/i;
           for (j=1;j<=maxim;j++)
               ndp[i*j]++;
           l[1]++;
           a[1][l[1]]=i;
        }
        else if(ndp[i]<8){l[ndp[i]]++;a[ndp[i]][l[ndp[i]]]=i;}

    scanf("%ld",&T);
    for (;T;T--){
        scanf("%ld %ld",&N,&k);
        low=1;
        high=l[k]+1;
        while (low<high){
              mid=(low+high)/2;
              if (a[k][mid]>N)
                 high=mid;
              else low=mid+1;
        }
        if (low<=l[k]+1 && a[k][low]==N)printf("%ld\n",N);
        else if (low>1)printf("%ld\n",a[k][low-1]);
             else printf("0\n");
    }
    
return 0;
}