#include <stdio.h>
#include <math.h>

long N,k,i,j,p[3000],ok,q,x,d;
long a[8][500000],T,low,mid,high,l[8],max;

int main(){
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    
    i=5;
    p[1]=2;
    p[2]=3;
    q=2;
    while (i<=15000){
          ok=0;
          j=1;
          while (p[j]*p[j]<=i){
                if (i%p[j]==0){ok=1;break;}
                ++j;
          }
          if (!ok){p[++q]=i;}
          i+=2;
    }
    l[0]=1;a[0][1]=1;
    for (i=1;i<=1000000;++i){
        x=i;j=1;d=0;

        while (x!=1&&p[j]*p[j]<=x){
              if (x%p[j]==0){
                 ++d;
                 while(x%p[j]==0)x/=p[j];
              }
              ++j;
        }
        if (x>1)++d;
        ++l[d];
        a[d][l[d]]=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;
}