#include <stdio.h>

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

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;
    }
    a[0][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++;
        a[d][0]++;
        a[d][a[d][0]]=i;
    }    
    
    scanf("%ld",&T);
    for (;T;T--){
        scanf("%ld %ld",&N,&k);
        low=1;
        high=a[k][0]+1;
        while (low<high){
              mid=(low+high)/2;
              if (a[k][mid]>N)
                 high=mid;
              else low=mid+1;
        }
        if (low<=a[k][0]+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;
}