//#include <stdio.h>
//#include <stdlib.h>
//#define NMAX 1000000 ///Cautare Binara!
//
//int ciur[NMAX+1],kmin[7];
//int main(){
//  int d,i,t,k,n,j;
//  FILE *fin, *fout;
//
//  ciur[1]=0;
//  for(d=2;d<=NMAX;d++){
//    if(ciur[d]==0)
//      for(i=d;i<=NMAX;i+=d)
//        ciur[i]++;
//    else if(kmin[ciur[d]]==0)
//      kmin[ciur[d]]=d;
//  }
//
//  fin=fopen("divprim.in","r");
//  fout=fopen("divprim.out","w");
//  fscanf(fin,"%d",&t);
//  for(i=0;i<t;i++){
//    fscanf(fin,"%d%d",&n,&k);
//    j=n;
//    if(kmin[k]>n)
//      fprintf(fout,"0\n");
//    else{
//      while(ciur[j]!=k)
//        j--;
//      fprintf(fout,"%d\n",j);
//    }
//  }
//  fclose(fin);
//  fclose(fout);
//  return 0;
//}

#include <stdio.h>
#include <stdlib.h>
#define NMAX 1000000 ///Cautare Binara!

int ciur[NMAX+1],m[7][NMAX];
int main(){
  int d,i,t,k,n,j;
  FILE *fin, *fout;

  ciur[1]=0;
  for(d=2;d<=NMAX;d++){
    if(ciur[d]==0)
      for(i=d;i<=NMAX;i+=d)
        ciur[i]++;
  }

  for(i=0;i<7;i++){
    for(j=1;j<NMAX;j++)
      if(ciur[j]==i)
        m[i][j]=j;
      else
        m[i][j]=m[i][j-1];
  }

  fin=fopen("divprim.in","r");
  fout=fopen("divprim.out","w");
  fscanf(fin,"%d",&t);
  for(i=0;i<t;i++){
    fscanf(fin,"%d%d",&n,&k);
    fprintf(fout,"%d\n",m[k][n]);
  }
  fclose(fin);
  fclose(fout);
  return 0;
}