#include <cstdio>
#define MAXN 1000000
#define MAXK 7
char nrdiv[MAXN+1];
int mat[MAXN+2][MAXK+1],prim[MAXN+1];
int main(){
    FILE*fi,*fout;
    int i,j,n,k,nr,x,t,aux;
    fi=fopen("divprim.in" ,"r");
    fout=fopen("divprim.out" ,"w");
    for(i=2;i*i<=MAXN;i++)
      if(prim[i]==0)
        for(j=2*i;j<=MAXN;j+=i)
            prim[j]=i;
    for(i=2;i<=MAXN;i++){
        nr=i;
        if(prim[nr]==0)
           nrdiv[i]=1;
        else{
           aux=-1;
           while(prim[nr]>0){
              if(aux!=prim[nr])
                 nrdiv[i]++;
              aux=prim[nr];
              nr=nr/prim[nr];
          }
          if(aux!=nr)
             nrdiv[i]++;
        }
    }
    for(i=1;i<=MAXK;i++){
         j=MAXN;
         mat[j+1][i]=MAXN+1;
         while(j>1){
             if(mat[j+1][i]<=j)
                mat[j][i]=mat[j+1][i];
             else{
                 x=j;
                 while(x>0&&nrdiv[x]!=i)
                    x--;
                 mat[j][i]=x;
             }
             j--;
         }
    }
    fscanf(fi,"%d" ,&t);
    while(t>0){
        t--;
        fscanf(fi,"%d%d" ,&n,&k);
        if(k==0)
           fprintf(fout,"1\n");
        else
           fprintf(fout,"%d\n" ,mat[n][k]);
    }
    fclose(fi);
    fclose(fout);
    return 0;
}